[Haskell-beginners] replacing fold with scan!

[Zhi An Ng]

​​
Hi,
The types of `foldr` and `scanr` are different:

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

I believe the reason is that `scanr` does something like a prefix sum,
https://en.wikipedia.org/wiki/Prefix_sum

So to get this to work, you need to change the type signature of filter''

filter'' :: (a -> Bool) -> [a] -> [[a]]

That's all.

Anyway you can try entering the definition of filter'' into ghci, and use
:t to let ghc figure our the type for you as well :)

Best,
Zhi An


On Thu, May 1, 2014 at 10:42 AM, raffa f <freitasraffa at gmail.com> wrote:

> hi everyone! here's my new problem. i wrote my version of filter:
>
> filter' :: (a -> Bool) -> [a] -> [a]
> filter' f = foldr (\x acc -> if f x then x:acc else acc) []
>
> and it works! however, i wanted to use scan too. so i just replaced foldr
> with scanr, to see what would happen:
>
> filter'' :: (a -> Bool) -> [a] -> [a]
> filter'' f = scanr (\x acc -> if f x then x:acc else acc) []
>
> but that doesn't work! ghci gives me this:
>
> folds.hs:15:59:
>     Couldn't match expected type `a' with actual type `[a0]'
>       `a' is a rigid type variable bound by
>           the type signature for filter'' :: (a -> Bool) -> [a] -> [a]
>           at folds.hs:14:13
>     In the second argument of `scanr', namely `[]'
>     In the expression:
>       scanr (\ x acc -> if f x then x : acc else acc) []
>     In an equation for filter'':
>         filter'' f = scanr (\ x acc -> if f x then x : acc else acc) []
> Failed, modules loaded: none.
>
> the problem seems to be with the start value of [], it seems? i don't
> understand, i thought scan and fold worked pretty much the same. i learned
> about these functions today, so i'm still trying to wrap my head around
> them...
>
> thank you!
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20140501/1a2a112e/attachment.html>