haskell的foldr总是采用双参数lambda吗？ [英] Does haskell's foldr always take a two-parameter lambda?

问题描述

Haskell newb here

我正在解决haskell中的这个问题：

 （**）消除列表元素的连续重复。 
如果列表包含重复的元素，则应该用元素的单个副本替换它们。元素的顺序不应该改变。 
 
示例：
 *（compress'（aaaabccaadeeee））
（ABCADE）
  

解决方案（我必须查找）使用foldr：

  compress'::公式a）=> [a]  - > [a] 
 compress'xs = foldr（\x acc  - > if x ==（head acc）then acc else x：acc）[last xs] xs 
  

根据解决方案，此foldr采用两个参数x和acc。似乎所有的foldr都采用这些参数;这有什么例外吗？就像需要3个或更多的foldr？如果不是这样，那么这个惯例是否是冗余的，并且可以用更少的代码来编写公式？ / code>接受2个参数的函数，但这并不妨碍它接受3个参数的函数，前提是该函数具有正确的类型签名。

如果我们有一个函数

  g :: x  - > y  - > z  - > w 
  

使用

  foldr ::（a  - > b  - > b） - > b  - > [a]  - > b 
  

我们想将 g 传递给 foldr ，则（a→b→b）→（x→y→z→w）（其中〜是类型相等）。由于 - > 是正确的关联，这意味着我们可以将 g 的签名写为

  x  - > y  - > （z  - > w）
  

和它的含义是一样的。现在我们已经产生了两个参数的函数，它们返回一个参数的函数。为了将它与 a - >类型统一起来， b - > b ，我们只需要排列参数：

  a  - > | x  - > 
 b  - > | y  - > 
 b | （z  - > w）
  

这意味着 b〜z - > ; w ，所以 y〜b〜z - > w 和 a〜x 所以 g 的类型必须是

  g :: x  - > （z→w）→> （z  - > w）
  

暗示

  foldr g ::（z  - > w） - > [x]  - > （z  - > w）
  

这当然不是不可能的，但更不可能。我们的累加器是一个函数，对我来说，这要求用DiffLists来演示：

  type DiffList a = [a]  - > [a] 
 
 append :: a  - > DiffList a  - > DiffList a 
 append x dl = \ xs  - > dl xs ++ [x] 
 
 reverse':: [a]  - > [a] 
 reverse'xs = foldr append（const []）xs $ [] 
  

请注意， foldr append（const []）xs 返回一个我们应用于 [] 来反转列表的函数。在这种情况下，我们给了 [a] - >类型的函数的别名。 [a] 称为 DiffList ，但它与写下

  append :: a  - > （[a]  - > [a]） - > [a]  - > [a] 
  

这是3个参数的函数。

Haskell newb here

I'm working on this problem in haskell:

(**) Eliminate consecutive duplicates of list elements.
If a list contains repeated elements they should be replaced with a single copy of the element. The order of the elements should not be changed.

Example:
* (compress '(a a a a b c c a a d e e e e))
(A B C A D E)

The solution (which I had to look up) uses foldr:

compress' :: (Eq a) => [a] -> [a]
compress' xs = foldr (\x acc -> if x == (head acc) then acc else x:acc) [last xs] xs

This foldr, according to the solution, takes two parameters, x and acc. It would seem like all foldr's take these parameters; is there any exception to this? Like a foldr that takes 3 or more? If not, is this convention redundant and can the formula be written with less code?

解决方案

foldr takes a function of 2 arguments, but this doesn't prevent it from taking a function of 3 arguments provided that function has the right type signature.

If we had a function

g :: x -> y -> z -> w

With

foldr :: (a -> b -> b) -> b -> [a] -> b

Where we want to pass g to foldr, then (a -> b -> b) ~ (x -> y -> z -> w) (where ~ is type equality). Since -> is right associative, this means we can write g's signature as

x -> y -> (z -> w)

and its meaning is the same. Now we've produced a function of two parameters that returns a function of one parameter. In order to unify this with the type a -> b -> b, we just need to line up the arguments:

a ->   |  x ->
b ->   |  y -> 
b      |  (z -> w)

This means that b ~ z -> w, so y ~ b ~ z -> w and a ~ x so g's type really has to be

g :: x -> (z -> w) -> (z -> w)

implying

foldr g :: (z -> w) -> [x] -> (z -> w)

This is certainly not impossible, although more unlikely. Our accumulator is a function instead, and to me this begs to be demonstrated with DiffLists:

type DiffList a = [a] -> [a]

append :: a -> DiffList a -> DiffList a
append x dl = \xs -> dl xs ++ [x]

reverse' :: [a] -> [a]
reverse' xs = foldr append (const []) xs $ []

Note that foldr append (const []) xs returns a function which we apply to [] to reverse a list. In this case we've given an alias to functions of the type [a] -> [a] called DiffList, but it's really no different than having written

append :: a -> ([a] -> [a]) -> [a] -> [a]

which is a function of 3 arguments.

这篇关于haskell的foldr总是采用双参数lambda吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！