But, of course, that's not very enlightening, so let's talk about how we might do it ourselves.
The list type, [], is a functor. We can implement fmap directly using recursion.
fmap :: (a -> b) -> [a] -> [b]
fmap _ [] = []
fmap f (x:xs) = f x : fmap f xs
Now we have a way of to do something for each element of a list. Great, that's how we'll apply our final operation, but we need to generate all of the argument lists as well. Specifically, we want to produce the Cartesian product.
cross :: [a] -> [b] -> [(a, b)]
And we can do so recursively as well, using our fmap function to help out.
Recursion on the first element. If the first argument is empty, then the Cartesian product is empty. If the first argument is nonempty, then the result should consist of the head paired with each (via fmap) element of the second argument, followed by the Cartesian product of the tail with the second list.
Now we have a way to get a [(Int, Int)]. And we want to multiply those elements, so it's just a matter of tying it all together.
apply2 :: (a -> b -> c) -> [a] -> [b] -> [c]
apply2 f xs ys = fmap (\(x, y) -> f x y) $ cross xs ys
Take the Cartesian product of the two lists, then apply our function f (uncurried) to each element.
This gives us our result, in a slightly different order than in your example. But it looks like you're sorting the results anyway, rather than producing them in an algorithmic order.
Now, let's talk about why liftA2 works. The list type is an example of an applicative functor, represented by the Applicative typeclass. Whereas fmap (which is part of Functor) takes a single function and maps it over a functor (in our case, over several elements of a list), the fundamental applicative operation is <*> (pronounced "ap"), whose signature is
fmap :: Functor f => (a -> b) -> f a -> f b
(<*>) :: Applicative f => f (a -> b) -> f a -> f b
Instead of mapping a single simple function over a functor value f a, we're mapping a function inside the functor f (a -> b) over a value also inside the functor f a. Now, this is a jumble of words, but in the case of lists it looks like
fmap :: (a -> b) -> [a] -> [b]
(<*>) :: [a -> b] -> [a] -> [b]
Rather than applying a single function to several elements, we're applying several functions to several elements. (<*>) is actually just our cross function written in a slightly different way. It's combining two lists using every combination to produce a result of some type. (In fact, the relationship between our cross and the applicative (<*>) is rather deep mathematically, due to the fact that (->) and (,) are adjoint to each other, but that's getting off track)
So (<*>) is just cross by another name. And liftA2 is defined as (something equivalent to)
liftA2 :: Applicative f => (a -> b -> c) -> f a -> f b -> f c
liftA2 f a b = fmap f a <*> b
It's just doing fmap and (<*>), which is basically what our apply2 function was doing to begin with. Again, it's slightly shuffled around since we're using (->) rather than (,) (since our "ap" operator applies a function rather than building a tuple), but it's exactly the same idea.
Certainly, the liftA2 approach is snazzy and short, but don't let it blind you. There's nothing wrong with a recursive approach, especially as you're learning. If apply2 makes more sense to you and my explanation above of the applicative functors was nonsense, then go for it. You can go a long way in Haskell learning about recursion and data structures before really grokking functors, and that's fine. But when you're ready, I recommend Typeclassopedia for an excellent summary of the Haskell typeclasses that represent functors, applicative functors, monads, and all of the other lesser-known abstractions available to the programmer.
发布评论
评论（1）
如果您很着急，则该功能称为
lifta2实际上是内置的。但是，当然，这不是很有启发性，所以让我们谈谈我们自己如何做的。
列表类型，
[]是函数。我们可以使用递归直接实现fmap。现在，我们有一种方法可以为列表的每个元素做某事。太好了，这就是我们将运用最终操作的方式，但是我们还需要生成所有参数列表。具体来说，我们想产生 cartesian产品。
我们也可以递归地这样做，使用我们的
fmap函数来提供帮助。第一个元素上的递归。如果第一个参数为空，则笛卡尔产品为空。如果第一个参数是非空的，则结果应由第二个参数的 配对（通过与第二个列表。
现在，我们有一种方法可以获得
[（int，int）]。我们想将这些元素倍增，所以这只是将所有内容绑在一起的问题。以两个列表的笛卡尔产品为例，然后将我们的函数
f（未验证）应用于每个元素。这使我们的结果与您的示例略有不同。但是看来您无论如何都要对结果进行排序，而不是按算法顺序产生它们。
现在，让我们谈谈为什么
lifta2有效。列表类型是应用函数的一个示例，由应用TypeClass。而fmap（这是fuctor）采用一个功能并将其映射通过函数（在我们的情况下，在列表的几个元素上），基本应用程序是＆lt;*＆gt;（发音为“ AP”），其签名为我们不是通过函数值映射单个简单函数
f a，而是在fightorf（a - ＆gt; b）内映射一个函数也内部f a。现在，这是一个单词的混乱，但是在列表的情况下，它看起来像是在几个元素上应用单个函数，我们将多个函数应用于几个元素。
（＆lt;*＆gt;）实际上只是我们的Cross以稍微不同的方式编写的功能。它使用各种组合来结合两个列表，以产生某种类型的结果。 （实际上，我们的cross与应用（＆lt;*＆gt;）之间的关系在数学上相当深，因为（ - ＆gt; ）和（，）彼此相邻，但这是偏离轨道），因此
（＆lt;*＆gt;）只是交叉用另一个名称。lifta2定义为（等同于）它只是在做
fmap和（＆lt;*＆gt;），这基本上是我们的<代码> apply2 函数是要开始的。同样，由于我们使用（ - ＆gt;）而不是（，）（因为我们的“ AP”操作员应用功能而不是构建元组），但这是完全相同的想法。当然，
lifta2方法很当时且短暂，但不要让它蒙蔽。递归方法没有错，尤其是在学习时。如果apply2对您更有意义，而我对应用程序函数的解释是胡说八道，那么请继续使用。您可以在Haskell学习有关递归和数据结构之前很长的路要走，然后才能真正掌握官能函数，这很好。但是，当您准备就绪时，我建议 typececlassopedia 用于代表函数，申请者，适用的haskell typeclasses的出色摘要程序员可以使用的函数，单调和所有其他鲜为人知的抽象。祝您好运，编码愉快！
If you're in a hurry, then the function is called
liftA2and it's actually built-in.But, of course, that's not very enlightening, so let's talk about how we might do it ourselves.
The list type,
[], is a functor. We can implementfmapdirectly using recursion.Now we have a way of to do something for each element of a list. Great, that's how we'll apply our final operation, but we need to generate all of the argument lists as well. Specifically, we want to produce the Cartesian product.
And we can do so recursively as well, using our
fmapfunction to help out.Recursion on the first element. If the first argument is empty, then the Cartesian product is empty. If the first argument is nonempty, then the result should consist of the head paired with each (via
fmap) element of the second argument, followed by the Cartesian product of the tail with the second list.Now we have a way to get a
[(Int, Int)]. And we want to multiply those elements, so it's just a matter of tying it all together.Take the Cartesian product of the two lists, then apply our function
f(uncurried) to each element.This gives us our result, in a slightly different order than in your example. But it looks like you're sorting the results anyway, rather than producing them in an algorithmic order.
Now, let's talk about why
liftA2works. The list type is an example of an applicative functor, represented by theApplicativetypeclass. Whereasfmap(which is part ofFunctor) takes a single function and maps it over a functor (in our case, over several elements of a list), the fundamental applicative operation is<*>(pronounced "ap"), whose signature isInstead of mapping a single simple function over a functor value
f a, we're mapping a function inside the functorf (a -> b)over a value also inside the functorf a. Now, this is a jumble of words, but in the case of lists it looks likeRather than applying a single function to several elements, we're applying several functions to several elements.
(<*>)is actually just ourcrossfunction written in a slightly different way. It's combining two lists using every combination to produce a result of some type. (In fact, the relationship between ourcrossand the applicative(<*>)is rather deep mathematically, due to the fact that(->)and(,)are adjoint to each other, but that's getting off track)So
(<*>)is justcrossby another name. AndliftA2is defined as (something equivalent to)It's just doing
fmapand(<*>), which is basically what ourapply2function was doing to begin with. Again, it's slightly shuffled around since we're using(->)rather than(,)(since our "ap" operator applies a function rather than building a tuple), but it's exactly the same idea.Certainly, the
liftA2approach is snazzy and short, but don't let it blind you. There's nothing wrong with a recursive approach, especially as you're learning. Ifapply2makes more sense to you and my explanation above of the applicative functors was nonsense, then go for it. You can go a long way in Haskell learning about recursion and data structures before really grokking functors, and that's fine. But when you're ready, I recommend Typeclassopedia for an excellent summary of the Haskell typeclasses that represent functors, applicative functors, monads, and all of the other lesser-known abstractions available to the programmer.Good luck, and happy coding!