60

私は常に新しい言語を学ぶことに興味を持っています。それは私をつま先立ちさせ、私をより良いプログラマーにする（私は信じています）という事実です。Haskellを征服しようとした私の試みは、これまでに2回行ったり来たりしており、再試行する時が来たと判断しました。3回目が魅力ですね。

いいえ。私は古いメモを読み直しました...そしてがっかりします:-(

前回私が信仰を失った問題は、簡単な問題でした。整数の順列です。つまり、整数のリストからリストのリストへ-それらの順列のリスト：

[int] -> [[int]]

これは実際には一般的な問題であるため、上記の「int」を「a」に置き換えても適用されます。

私のメモから：

私は最初に自分でコーディングし、成功します。フラ！

私は私の解決策を私の親友であるHaskellの第一人者に送ります。それは通常、教祖から学ぶのに役立ちます。彼は私にこれを送ってくれます。ニーズ"。そのすべてのために、私は最近クールエイドを飲みました、行きましょう：

permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
   where ins x []     = [[x]]
         ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

うーん。これを分解してみましょう：

bash$ cat b.hs
ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]

bash$ ghci
Prelude> :load b.hs
[1 of 1] Compiling Main             ( b.hs, interpreted )
Ok, modules loaded: Main.

*Main> ins 1 [2,3]
[[1,2,3],[2,1,3],[2,3,1]]

OK、これまでのところ、とても良いです。「ins」の2行目を理解するのに少し時間がかかりましたが、OK：リスト内のすべての可能な位置に1番目の引数が配置されます。涼しい。

ここで、foldrとconcatMapを理解します。「実世界ハスケル」では、DOTが説明されました...

(f . g) x

...の別の構文として...

f (g x)

そして、教祖が送信したコードでは、DOTはフォルダーから使用され、「ins」関数はフォールド「collapse」として機能します。

*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

OK、DOTが教祖によってどのように使用されているかを理解したいので、DOTの定義に従って同等の式を試してみます。（f。g）x = f（gx）.. ..

*Main> concatMap (ins 1 [[2,3]])

<interactive>:1:11:
     Couldn't match expected type `a -> [b]'
            against inferred type `[[[t]]]'
     In the first argument of `concatMap', namely `(ins 1 [[2, 3]])'
     In the expression: concatMap (ins 1 [[2, 3]])
     In the definition of `it': it = concatMap (ins 1 [[2, 3]])

何！？！なんで？OK、concatMapの署名を確認すると、ラムダとリストが必要であることがわかりましたが、それは人間の考えにすぎません。GHCはどのように対処しますか？上記のDOTの定義によると...

(f.g)x = f(g x),

...私がしたことは有効でした。

(concatMap . ins) x y = concatMap (ins x y)

頭を掻く...

*Main> concatMap (ins 1) [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

だから...DOTの説明は明らかに単純すぎました...DOTは、私たちが実際に「イン」をカレーして最初の引数を「食べる」ことを望んでいたことを理解するのに十分賢いはずです-したがって、 [t]を操作したい（そして、可能なすべての位置に「1」を「散在」させたい）。

しかし、これはどこで指定されましたか？私たちが呼び出したとき、GHCはどのようにしてこれを行うことを知っていましたか？

*Main> (concatMap . ins) 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]

「ins」署名はどういうわけかこれを伝えましたか...「私の最初の議論を食べる」ポリシー？

*Main> :info ins
ins :: t -> [t] -> [[t]]        -- Defined at b.hs:1:0-2

特別なことは何もありません。「ins」は、「t」、「t」のリストを受け取り、すべての「散在」を含むリストの作成に進む関数です。「最初の議論を食べて、それをカレーする」ことについては何もありません。

だからそこに...私は困惑しています。私は（コードを1時間見てから！）何が起こっているのか理解していますが...全能の神...おそらくGHCは、「剥がす」ことができる引数の数を確認しようとしますか？

  let's try with no argument "curried" into "ins",
  oh gosh, boom, 
  let's try with one argument "curried" into "ins",
  yep, works,
  that must be it, proceed)

もう一度-イケ...

そして、私は常に私が学んでいる言語を私がすでに知っているものと比較しているので、Pythonで「ins」はどのように見えるでしょうか？

a=[2,3]
print [a[:x]+[1]+a[x:] for x in xrange(len(a)+1)]

[[1, 2, 3], [2, 1, 3], [2, 3, 1]]

正直に言って、今...どちらが簡単ですか？

つまり、私はHaskellの初心者であることを知っていますが、私は馬鹿のように感じます... 1時間に4行のコードを見て、コンパイラが...何かが見つかるまで、さまざまな解釈を試みます。クリック」？

リーサルウェポンから引用すると、「私はこれには年を取りすぎています」...

4

3 に答える 3

93 
(f . g) x = f (g x)

これは本当です。あなたはそれから結論を下しました

(f . g) x y = f (g x y)

真でなければなりませんが、そうではありません。実際、次のことが当てはまります。

(f . g) x y = f (g x) y

これは同じではありません。

なぜこれが本当ですか？それ(f . g) x yはと同じであり、それをに減らすことができることが((f . g) x) yわかっているので、これも。と同じです。(f . g) x = f (g x)(f (g x)) yf (g x) y

したがって(concatMap . ins) 1 [[2,3]]、と同等concatMap (ins 1) [[2,3]]です。ここでは魔法はありません。

これにアプローチする別の方法は、タイプを使用することです。

.タイプ(b -> c) -> (a -> b) -> a -> cがconcatMapあり、タイプ(x -> [y]) -> [x] -> [y]がinsあり、タイプがありt -> [t] -> [[t]]ます。したがって、引数として、および引数として使用するconcatMapと、b -> cは、になり、になります（=および=を使用）。insa -> batb[t] -> [[t]]c[[t]] -> [[t]]x[t]y[t]

したがって、のタイプはconcatMap . insですt -> [[t]] -> [[t]]。これは、（何でも）リストのリストを取得し、（同じタイプの）リストのリストを返す関数を意味します。

于 2010-10-07T17:24:47.210 に答える
12

2セント追加したいのですが。.質問と回答は、関数呼び出しを再配置することで奇妙なことをする魔法の演算子のように聞こえます。そうではありません。.単なる関数合成です。Pythonでの実装は次のとおりです。

def dot(f, g):
    def result(arg):
        return f(g(arg))
    return result

g引数に適用され、結果に適用され、適用さfれた結果を返す新しい関数を作成するだけfです。

つまり(concatMap . ins) 1 [[2, 3]]、関数を作成し、concatMap . insそれを引数1とに適用します[[2, 3]]。concatMap (ins 1 [[2,3]])代わりに言っているのは、Haskellの恐ろしいエラーメッセージからわかるように、とに適用しconcatMapた結果に関数を適用することです。これはまったく異なります。ins1[[2, 3]]

更新：これをさらに強調します。あなたはそれ(f . g) xがの別の構文だと言いましたf (g x)。これは間違っています！.関数は英数字以外の名前を付けることができるため（、なども関数名にすることができます）、は単なる関数>><です..。

于 2010-10-07T19:05:49.093 に答える
5

あなたはこの問題を考えすぎています。あなたは単純な等式推論を使用してそれをすべて解決することができます。ゼロから試してみましょう：

permute = foldr (concatMap . ins) [[]]

これは簡単に次のように変換できます。

permute lst = foldr (concatMap . ins) [[]] lst

concatMap次のように定義できます。

concatMap f lst = concat (map f lst)

リストで機能する方法foldrは次のとおりです（たとえば）：

-- let lst = [x, y, z]
foldr f init lst
= foldr f init [x, y, z]
= foldr f init (x : y : z : [])
= f x (f y (f z init))

だから何かのような

permute [1, 2, 3]

になります：

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))

最初の式を試してみましょう。

(concatMap . ins) 3 [[]]
= (\x -> concatMap (ins x)) 3 [[]]  -- definition of (.)
= (concatMap (ins 3)) [[]]
= concatMap (ins 3) [[]]     -- parens are unnecessary
= concat (map (ins 3) [[]])  -- definition of concatMap

今ins 3 [] == [3]、そう

map (ins 3) [[]] == (ins 3 []) : []  -- definition of map
= [3] : []
= [[3]]

したがって、元の式は次のようになります。

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 
    ((concatMap . ins) 2
       ((concatMap . ins) 3 [[]]))
= (concatMap . ins) 1 
    ((concatMap . ins) 2 [[3]]

やってみましょう

(concatMap . ins) 2 [[3]]
= (\x -> concatMap (ins x)) 2 [[3]]
= (concatMap (ins 2)) [[3]]
= concatMap (ins 2) [[3]]     -- parens are unnecessary
= concat (map (ins 2) [[3]])  -- definition of concatMap
= concat (ins 2 [3] : [])
= concat ([[2, 3], [3, 2]] : [])
= concat [[[2, 3], [3, 2]]]
= [[2, 3], [3, 2]]

したがって、元の式は次のようになります。

foldr (concatMap . ins) [[]] [1, 2, 3]
= (concatMap . ins) 1 [[2, 3], [3, 2]]
= (\x -> concatMap (ins x)) 1 [[2, 3], [3, 2]]
= concatMap (ins 1) [[2, 3], [3, 2]]
= concat (map (ins 1) [[2, 3], [3, 2]])
= concat [ins 1 [2, 3], ins 1 [3, 2]] -- definition of map
= concat [[[1, 2, 3], [2, 1, 3], [2, 3, 1]], 
          [[1, 3, 2], [3, 1, 2], [3, 2, 1]]]  -- defn of ins
= [[1, 2, 3], [2, 1, 3], [2, 3, 1], 
   [1, 3, 2], [3, 1, 2], [3, 2, 1]]

ここには魔法のようなものは何もありません。簡単に推測できるので混乱しているかもしれconcatMap = concat . mapませんが、そうではありません。同様に、のようconcatMap f = concat . (map f)に見えるかもしれませんが、これも真実ではありません。等式推論はその理由を示します。

于 2010-10-09T21:47:18.150 に答える