[Haskell-beginners] replacing fold with scan!

[Mateusz Kowalczyk]

On 05/01/2014 04:42 AM, raffa f 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
> 

Simply look at the types:

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

You should now be able to see why your filter'' can't have the same type
signature as your filter'.

You could just ask what GHCi thinks about your function by removing the
signature:

Prelude> :t \f -> scanr (\x acc -> if f x then x:acc else acc) []
\f -> scanr (\x acc -> if f x then x:acc else acc) []
  :: (a -> Bool) -> [a] -> [[a]]

So you're saying that your function takes (a -> Bool) and [a] and
returns [a] but that's not the case: it takes (a -> Bool) and [a] and
returns [[a]].

-- 
Mateusz K.