60

我总是对学习新语言感兴趣,这一事实让我保持警觉,并使我(我相信)成为一个更好的程序员。我征服 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 行代码一个小时,最终假设编译器……尝试各种解释,直到找到“点击”?

引用致命武器的话,“我对这个太老了”......

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

这是不一样的。

为什么这是真的?Well与 and(f . g) x y相同((f . g) x) y,因为我们知道(f . g) x = f (g x)可以将其简化为(f (g x)) y,这又与 相同f (g x) y

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

解决此问题的另一种方法是通过以下类型:

.有型(b -> c) -> (a -> b) -> a -> cconcatMap有型(x -> [y]) -> [x] -> [y]ins有型t -> [t] -> [[t]]。因此,如果我们使用concatMapasb -> c参数和insasa -> b参数,则a变为tb变为[t] -> [[t]]c变为[[t]] -> [[t]](使用x=[t]y= [t])。

所以concatMap . insis的类型t -> [[t]] -> [[t]],这意味着一个函数接受一个whatevers和一个列表列表(whatevers)并返回一个列表列表(相同类型的)。

于 2010-10-07T17:24:47.210 回答
12

我想加两分钱。问题和答案听起来像是.一些神奇的运算符,它通过重新安排函数调用来做奇怪的事情。事实并非如此。.只是功能组合。这是 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]])你是在说,将函数应用于应用到concatMap的结果和- 完全不同,正如你从 Haskell 的可怕错误消息中发现的那样。ins1[[2, 3]]

更新:进一步强调这一点。你说那(f . g) xf (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 回答