问题描述
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吗?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!