我总是对学习新语言感兴趣,这一事实让我保持警觉,并使我(我相信)成为一个更好的程序员。我征服 Haskell 的尝试来来去去——到目前为止已经两次——我决定是时候再试一次了。第三次是魅力,对吧?
没有。我重新阅读了我的旧笔记......并感到失望:-(
上次让我失去信心的问题是一个简单的问题:整数的排列。即从整数列表到列表列表 - 它们的排列列表:
[int] -> [[int]]
这实际上是一个通用问题,因此将上面的 'int' 替换为 'a' 仍然适用。
从我的笔记中:
我自己先编码,我成功了。欢呼!
我把我的解决方案发给了我的一个好朋友——Haskell 大师,它通常有助于向大师学习——他给我发了这个,有人告诉我,“表达了语言的真正力量,使用通用工具来编写你的代码需要”。为了它,我最近喝了kool-aid,走吧:
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”的第二行,但是好的:它将第一个 arg 放在列表中所有可能的位置。凉爽的。
现在,要了解 foldr 和 concatMap。在“Real world Haskell”中,DOT 被解释了......
(f . g) x
...作为...的另一种语法
f (g x)
在大师发送的代码中,DOT 是从一个 foldr 中使用的,“ins”函数作为折叠“collapse”:
*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]
好的,既然我想了解大师是如何使用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]])
什么!?!为什么?好的,我检查了concatMap的签名,发现它需要一个lambda和一个列表,但这只是人的想法;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 必须足够聪明才能理解我们实际上希望“ins”被柯里化并“吃掉”第一个参数 - 因此成为一个函数想要对 [t] 进行操作(并在所有可能的位置上“穿插”它们)。
但是这是在哪里指定的?当我们调用时,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”列表,然后继续创建一个包含所有“interspersals”的列表。没有什么关于“吃掉你的第一个论点并把它赶走”。
所以那里......我很困惑。我明白(看了一个小时的代码之后!)发生了什么,但是......上帝全能......也许 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)
再次 - 哎呀...
而且由于我总是将我正在学习的语言与我已经知道的语言进行比较,那么“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 行代码一个小时,最终假设编译器……尝试各种解释,直到找到“点击”?
引用致命武器的话,“我对这个太老了”......