Haskell函数的应用和currying
我总是对学习新的语言感兴趣，这个事实让我感到脚踏实地，让我（我相信）成为一个更好的程序员。 我试图征服Haskell来来去去 – 曾经两次 – 我决定是时候再试一次。 第三次的魅力吧？
不。 我重读了我的旧笔记，并感到失望:-(
上次让我失去信心的问题很简单：整数的排列。 即从整数列表到列表列表 – 它们的排列列表：
[int] -> [[int]] 这实际上是一个通用的问题，所以用'a'取代'int'仍然适用。
从我的笔记：
我自己编码，我成功了。 欢呼！
我把我的解决scheme发给我的一个好朋友 – 哈斯克尔大师，通常有助于向大师学习 – 他告诉我，这是我所知道的，“expression了语言的真正力量，使用通用设施来编码需要”。 所有这一切，我最近喝了这个苦工，走吧：
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]]
好的，到目前为止，那么好。 花了我一分钟来了解“ins”的第二行，但是OK：它将第一个arg放在列表中所有可能的位置。 凉。
现在，了解foldr和concatMap。 在“真实世界Haskell”中，DOT被解释了…
(f . g) x
…只是另一种语法…
f (gx)
而在上师的代码中，DOT被用在foldr上，而“ins”函数被用作折叠的“折叠”：
*Main> let g=concatMap . ins *Main> g 1 [[2,3]] [[1,2,3],[2,1,3],[2,3,1]]
好的，因为我想了解古茹是如何使用DOT的，所以我尝试了根据DOT定义的等价expression式（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]])
什么！？！ 为什么？ 好，我检查concatMap的签名，发现它需要一个lambda和一个列表，但这只是一个人的思维; GHC如何应对？ 根据以上DOT的定义…
(fg)x = f(gx),
…我所做的是有效的，取而代之的是：
(concatMap . ins) xy = concatMap (ins xy)
抓头…
*Main> concatMap (ins 1) [[2,3]] [[1,2,3],[2,1,3],[2,3,1]]
所以…… DOT的解释显然太简单了… DOT一定要有足够的聪明才能理解我们实际上是想让“ins”被卷走，“吃”第一个参数 – 从而成为一个函数，只有想要在[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'的列表，然后创build一个带有所有“interspersals”的列表。 没有什么关于“吃你的第一个争论，把它咖喱”。
所以那里…我很困惑。 我明白了（看了一小时后的代码！）但是……全能的上帝……也许GHC试图去看看它能“剥离”多less个论据？
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)
再说一遍…
而且由于我总是将我正在学习的语言与我已经知道的语言进行比较，那么“ins”会在Python中看起来如何呢？
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的新手，但是我觉得自己像一个白痴… …查看4行代码一小时，最后假定编译器…尝试各种解释，直到find“点击“？
引用致命的武器，“我太老了…”
(f . g) x = f (gx)
这是真的。 你从那里得出结论
(f . g) xy = f (gxy)
也必须是真实的，但事实并非如此。 事实上，以下是事实：
(f . g) xy = f (gx) y
这是不一样的。
为什么这是真的？ 那么(f . g) xy和((f . g) x) y ，因为我们知道(f . g) x = f (gx)我们可以把它减less到(f (gx)) y和f (gx) y 。
所以(concatMap . ins) 1 [[2,3]]相当于concatMap (ins 1) [[2,3]] 。 这里没有魔法。
解决这个问题的另一种方法是通过以下types：
. 具有types(b -> c) -> (a -> b) -> a -> c ， concatMap的types是(x -> [y]) -> [x] -> [y]inputt -> [t] -> [[t]] 。 因此，如果我们使用concatMap作为b -> c参数，并使用ins作为a -> b参数，则a变成t ， b变成[t] -> [[t]] ， c变成[[t]] -> [[t]] （其中x = [t]和y = [t] ）。
所以concatMap . ins的typesconcatMap . ins concatMap . ins是t -> [[t]] -> [[t]] ，这意味着一个函数将一个列表（whatevers）和一个列表（相同types的列表）返回。
我想补充我的两分钱。 问题和答案听起来像. 是一些神奇的操作员，通过重新安排函数调用来做一些奇怪的事情。 事实并非如此。 . 只是function组成。 这是Python中的一个实现：
def dot(f, g): def result(arg): return f(g(arg)) return result
它只是创build一个新的函数，将g应用于参数，将f应用于结果，并返回应用f的结果。
所以(concatMap . ins) 1 [[2, 3]]是说：创build一个函数concatMap . ins 并将其应用于参数1和[[2, 3]] 。 当你做concatMap (ins 1 [[2,3]])你应该把函数concatMap应用到1和[[2, 3]] – 完全不同，就像你想象的那样哈斯克尔的可怕的错误消息。
更新：进一步强调这一点。 你说(f . g) x是f (gx)另一个语法。 这是错误的 ！ . 只是一个函数，因为函数可以具有非字母数字名称（ >>< ， ..等，也可以是函数名称）。
你正在解决这个问题。 你可以使用简单的等式推理来解决这个问题。 让我们从头开始尝试：
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 : []) = fx (fy (fz init))
所以像
permute [1, 2, 3]
变为：
foldr (concatMap . ins) [[]] [1, 2, 3] = (concatMap . ins) 1 ((concatMap . ins) 2 ((concatMap . ins) 3 [[]]))
我们来看看第一个expression式：
(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 = concat . map ，但事实并非如此。 同样，它可能看起来像concatMap f = concat . (map f) concatMap f = concat . (map f) ，但是这也是不正确的。 等式推理会告诉你为什么。
