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 -> c，concatMap有型(x -> [y]) -> [x] -> [y]，ins有型t -> [t] -> [[t]]。因此，如果我们使用concatMapasb -> c参数和insasa -> b参数，则a变为t，b变为[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) 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 回答