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)) yf (gx) y

所以(concatMap . ins) 1 [[2,3]]相当于concatMap (ins 1) [[2,3]] 。 这里没有魔法。

解决这个问题的另一种方法是通过以下types:

. 具有types(b -> c) -> (a -> b) -> a -> cconcatMap的types是(x -> [y]) -> [x] -> [y]inputt -> [t] -> [[t]] 。 因此,如果我们使用concatMap作为b -> c参数,并使用ins作为a -> b参数,则a变成tb变成[t] -> [[t]]c变成[[t]] -> [[t]] (其中x = [t]y = [t] )。

所以concatMap . ins的typesconcatMap . ins concatMap . inst -> [[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) xf (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) ,但是这也是不正确的。 等式推理会告诉你为什么。