8

I'm learning Haskell. This is a trivial example but I'd like to understand the concept why I can't use the pattern matching inside the lambda function in the following example (i.e., why does the filterfold' function run but filterfold' gives a runtime error):

-- Runs
filterfold' :: (a -> Bool) -> [a] -> [a]
filterfold' p zs = foldr (\y zs -> if (p y) then y:zs else zs) [] zs

-- Runtime error: Non-exhaustive patterns in lambda
filterfold :: (a -> Bool) -> [a] -> [a]
filterfold p (z:zs) = foldr (\y (z:zs) -> if (p y) then y:(z:zs) else (z:zs)) [] (z:zs)
Daniel
  • 3,758
  • 3
  • 22
  • 43

1 Answers1

9

you can use it but as the compiler tells you you are missing a case (when the input is [])

See if you say z:zs it will try to match this pattern with the input-list - if you

  • input [1,2,3] = 1:[2,3] you get z=1 and zs=[2,3]
  • but when input [] you cannot get a z and zs so that z:zs = [] (technically they are based on different constructors of the list-datatype)

So at runtime it will not know how to handle this case/pattern when it sees [] and throw the exception.

if you look closely at your example you should see that you never actually use the parts anyway (meaning z or zs - you only use them as z:zs again) so I cannot tell you how to do it better

anyway you can use the case - expression inside of an lambda:

... = foldr (\ x zs -> case zs of
                         [] -> ...
                         z:zs -> ...

or you can use the LambdaCase extension to make it a bit shorter.

Igor Golovin
  • 64
  • 1
  • 8
Random Dev
  • 51,810
  • 9
  • 92
  • 119
  • So, the zs from the filterfold function's argument is in scope but instead of using the 'z' from filterfold it tries to perform pattern matching locally inside the lambda? – Daniel Jul 24 '16 at 12:22
  • 1
    yes the `z` and `zs` inside the lambda will be different ones (`foldr` will *provide* them) - that's why you should not reuse parameter/argument names for lambda-arguments - you *introduce* those names with your lambda and will hide the once from the outer-scope - so if you want to (re)use the `z` and `zs` from the outer-scope in `filterfold` you should just rename it into `foldr (\y ys -> ...)` (or whatever name you like different from `p`, `z`, `zs` and `y` ;) ) – Random Dev Jul 24 '16 at 12:26
  • but please note: if you don't actually need the second argument of function (the lambda) you are giving to `foldr` then you probably don't need the `foldr` in the first place as you are only acting on the `head` of the list if it's not-empty or defaulting to the second argument of `foldr` – Random Dev Jul 24 '16 at 12:29
  • Understand that filterfold' is a cleaner version than filterfold. This is just for a conceptual understanding. So, in filterfold' I could define for foldr the lambda function as (\y qs -> if (p y) then y:qs else qs) with different argument names. I understand that the y argument in the lambda will be the current element in the list 'zs'. But what is qs? Why is it same as the zs list? – Daniel Jul 24 '16 at 12:53
  • you can think of the `qs` as the accumulator or state you pass around - so you start at the right end of your input list and replace the `[]` there with the second parameter to `foldr` (here '[]` too) - then you take the last element `y` and `qs=[]` and compine those with your lambda into a new `qs` ... repeat that to your first element in the list – Random Dev Jul 24 '16 at 14:05
  • just look for tuturials/articles on list-fold - you fill find plenty – Random Dev Jul 24 '16 at 14:06
  • Thanks, Carsten! I also figured out how the lambda function for foldr works (and what the arguments refer to) and posted it: http://stackoverflow.com/questions/5726445/how-would-you-define-map-and-filter-using-foldr-in-haskell/38554918#38554918 – Daniel Jul 25 '16 at 02:43