Haskell函数的应用和currying [英] Haskell function application and currying
问题描述
我总是对学习新语言感兴趣，这一事实让我感到脚踏实地，并使我（我相信）成为一名更好的程序员。我试图征服Haskell来来去去 - 两次到目前为止 - 我决定是时候再试一次。第三次的魅力，对不对？
没有。我重读了我的旧笔记...并且感到失望： - （
）上次让我失去信心的问题很简单：整数的排列。
即从整数列表到列表列表 - 它们的列表列表：
[int] - > [[int]]
这实际上是一个通用的问题，上面有'a'，仍然适用。
从我的笔记：
我先在我的自己，我成功了！Hurray！
我把我的解决方案发给我的一个好朋友 - 哈斯克尔大师，通常有助于向大师学习 - 他向我发送这个，据我所知，表达了语言的真正力量，使用通用设施来编写你的需求。所有这一切，我最近喝了这个kool-aid，让我们开始吧：
permute :: [a] - > [[a]]
permute = foldr（concatMap.ins）[[]]
where ins x [] = [[x]]
ins x（y：ys）=（x：y：ys）：[y：re s | res< - ins x ys]
嗯。
让我们来分析一下：
bash $ cat b.hs
ins x [] = [[ （y：ys）=（x：y：ys）：[y：res | x] res< - ins x ys]
bash $ ghci
前奏> ：加载b.hs
[1的1]编译主（b.hs，解释）
好吧，模块加载：主。
*主要> ins 1 [2,3]
[[1,2,3]，[2,1,3]，[2,3,1]]
好的，到目前为止，非常好。花了我一分钟来理解ins的第二行，但是OK：
它将第一个参数放在列表中的所有可能位置。酷。
现在，了解foldr和concatMap。在真实世界Haskell中，DOT被解释了......
（f。g）x
...只是另一种语法...
f（gx）
在古鲁发送的代码中，DOT被用在foldr上，用ins函数作为折叠collapse：
* Main>让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：
无法匹配期望的类型`a - > [b]'
对比推断类型`[[[t]]]'
在`concatMap'的第一个参数中，即`（ins 1 [[2,3]]）
在表达式中：concatMap（ins 1 [[2，3]]）
在`it'的定义中：it = concatMap（ins 1 [[2,3]]）
什么！？！为什么？
好的，我检查了concatMap的签名，发现它需要一个lambda和一个列表，但这只是
只是一个人的思维; GHC如何应对？根据以上DOT的定义...
$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ code>
...我做的是有效的，替换方式：
（concatMap .ins）xy = concatMap（ins xy）
抓头...
* Main> concatMap（ins 1）[[2,3]]
[[1,2,3]，[2,1,3]，[2,3,1]]
过于简单化... 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]] - 定义在b.hs：1：0-2
t没什么特别的 - ins是一个函数，需要't'，
a列出't'，然后创建一个包含所有interspersals的列表。没有关于吃掉你的第一个理由并把它咖喱掉。
所以......我很困惑。我明白了（在查看代码一小时之后），但是......上帝全能的......也许GHC试图查看它可以剥离多少个参数？
让我们尝试没有参数curriedintoins，
哦gosh，boom，
让我们尝试一个参数curried进入ins，
yep，works，
必须是它，继续）
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行代码，并最终假定编译器...尝试各种解释直到找到b
$ b
为了引用致命武器，我太老了...
解决方案
（f。g）x = f（gx）
这是真的。你从中得出结论：
（f。g）xy = f（gxy）
也必须为真，但事实并非如此。事实上，以下是真的：
（f。g）xy = f（gx）y
这是不一样的。
为什么这是真的？那么（f。g）xy 与（（f。g）x）y 相同，因为我们知道我们可以将它减少到（f（gx））y ，这与 f（gx）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]] 。因此，如果我们使用 concatMap 作为 b - > c 参数和 ins 作为 a - > b 参数，则 a 变为 t ， b 变成 [t] - > [[t]] 和 c 变成 [[t]] - > [[t]] （含 x = [t] 和 y = [t] ）。
c $ c> concatMap。 ins
是 t - > [[t]] - > [[t]] ，这意味着一个函数将一个列表（发起者）列表并返回列表（相同类型的列表）。
I am always interested in learning new languages, a fact that keeps me on my toes and makes me (I believe) a better programmer. My attempts at conquering Haskell come and go - twice so far - and I decided it was time to try again. 3rd time's the charm, right?
Nope. I re-read my old notes... and get disappointed :-(
The problem that made me lose faith last time, was an easy one: permutations of integers.
i.e. from a list of integers, to a list of lists - a list of their permutations:
[int] -> [[int]]
This is in fact a generic problem, so replacing 'int' above with 'a', would still apply.
From my notes:
I code it first on my own, I succeed. Hurrah!
I send my solution to a good friend of mine - Haskell guru, it usually helps to learn from gurus - and he sends me this, which I am told, "expresses the true power of the language, the use of generic facilities to code your needs". All for it, I recently drank the kool-aid, let's go:
permute :: [a] -> [[a]]
permute = foldr (concatMap.ins) [[]]
where ins x [] = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]
Hmm.
Let's break this down:
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]]
OK, so far, so good. Took me a minute to understand the second line of "ins", but OK:
It places the 1st arg in all possible positions in the list. Cool.
Now, to understand the foldr and concatMap. in "Real world Haskell", the DOT was explained...
(f . g) x
...as just another syntax for...
f (g x)
And in the code the guru sent, DOT was used from a foldr, with the "ins" function as the fold "collapse":
*Main> let g=concatMap . ins
*Main> g 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]
OK, since I want to understand how the DOT is used by the guru, I try the equivalent expression according to the DOT definition, (f . g) x = f (g x) ...
*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]])
What!?! Why?
OK, I check concatMap's signature, and find that it needs a lambda and a list, but that's
just a human thinking; how does GHC cope? According to the definition of DOT above...
(f.g)x = f(g x),
...what I did was valid, replace-wise:
(concatMap . ins) x y = concatMap (ins x y)
Scratching head...
*Main> concatMap (ins 1) [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]
So... The DOT explanation was apparently
too simplistic... DOT must be somehow clever enough to understand
that we in fact wanted "ins" to get curri-ed away and "eat" the first
argument - thus becoming a function that only wants to operate on [t]
(and "intersperse" them with '1' in all possible positions).
But where was this specified? How did GHC knew to do this, when we invoked:
*Main> (concatMap . ins) 1 [[2,3]]
[[1,2,3],[2,1,3],[2,3,1]]
Did the "ins" signature somehow conveyed this... "eat my first argument" policy?
*Main> :info ins
ins :: t -> [t] -> [[t]] -- Defined at b.hs:1:0-2
I don't see nothing special - "ins" is a function that takes a 't',
a list of 't', and proceeds to create a list with all "interspersals". Nothing about "eat your first argument and curry it away".
So there... I am baffled. I understand (after an hour of looking at the code!) what goes on, but... God almighty... Perhaps GHC makes attempts to see how many arguments it can "peel off"?
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)
Again - yikes...
And since I am always comparing the languages I am learning with what I already know, how would "ins" look in 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]]
Be honest, now... which is simpler?
I mean, I know I am a newbie in Haskell, but I feel like an idiot... Looking at 4 lines of code for an hour, and ending up assuming that the compiler... tries various interpretations until it finds something that "clicks"?
To quote from Lethal weapon, "I am too old for this"...
解决方案 (f . g) x = f (g x)
This is true. You concluded from that that
(f . g) x y = f (g x y)
must also be true, but that is not the case. In fact, the following is true:
(f . g) x y = f (g x) y
which is not the same.
Why is this true? Well (f . g) x y is the same as ((f . g) x) y and since we know that (f . g) x = f (g x) we can reduce that to (f (g x)) y, which is again the same as f (g x) y.
So (concatMap . ins) 1 [[2,3]] is equivalent to concatMap (ins 1) [[2,3]]. There is no magic going on here.
Another way to approach this is via the types:
. has the type (b -> c) -> (a -> b) -> a -> c, concatMap has the type (x -> [y]) -> [x] -> [y], ins has the type t -> [t] -> [[t]]. So if we use concatMap as the b -> c argument and ins as the a -> b argument, then a becomes t, b becomes [t] -> [[t]] and c becomes [[t]] -> [[t]] (with x = [t] and y = [t]).
So the type of concatMap . ins is t -> [[t]] -> [[t]], which means a function taking a whatever and a list of lists (of whatevers) and returning a list of lists (of the same type).
这篇关于Haskell函数的应用和currying的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
