Let's do this step by step. We use the following list: [1,2,3] foldr takes three arguments: foldr :: (a -> b -> b) -> b -> [a] -> b The last of the three has type [a]. This means, the fold expects a list as an argument here. The lower case letter `a` is the type of the items in the list. In our case this is `Int`, but we could pass it other lists with other element types. The second argument of the fold has type `b`, this is the result type we'd like to get from the fold. In our case this is `Maybe Int` since we want to know from the result, whether the list was empty or not. Nothing in case of an empty list, Just x with x being the right-most item in the non-empty case. The first argument of the fold is a higher order function. It accepts an argument of type `a` (the element type of the list) and of type `b` (the result type of the fold) and should return a value of type `b`. In our example, `a` is equal to `Int` and b is equal to `Maybe Int`. Therefore, the following cannot possibly work:
acc a acc = if null a then Nothing else if (null (tail a)) then (Just
the first argument of acc (the value `a` in your implementation) has type `a` (note the distinction between a value and a type, both have the same name here, but that doesn't need to be the case. You could rename the value to x or foo or whatever). In our case, the type `a` is `Int` since we fold over a list of Ints. If we were to fold over a list of Strings, type `a` would be equal to `String`. Note however, that since `a` can be anything (Int, String etc, depending on the element type of your list), you cannot possibly call `null` on it. null takes a list as an argument, but `a` is not necessarily a list. It's the type of the list's elements, not the whole list. You do not pass the whole list to the accumulator. You only pass it the list's element in single file. Now, what happens, when we fold over the list? Since we fold from the right, our accumulator is passed two arguments: The last value of the list and the initial value of type `b` (in our case `Nothing`). acc 3 Nothing = ??? What should be the result of this? Clearly you'd like to keep the 3 as it is actually the result you are looking for. But you cannot return the 3 directly. The return type of our function must be `Maybe Int` and the type of `3` is `Int`. We first must wrap the `3` in a `Maybe`. There is only one way to do that: acc 3 Nothing = Maybe 3 (This is pseudocode an will not compile. The real implementation follows below) Now comes the next item in the list: `2`. Function acc gets called again, this time with `2` as its first argument, and the result of our fold so far which is `Just 3` acc 2 (Just 3) = ??? Clearly we do not want to lose the `3`, it's the result we are looking for after all! acc 2 (Just 3) = Just 3 Finally, the last item (from the right) in the list comes along: acc 1 (Just 3) = Just 3 Again we let it pass and get Just 3 as the result. This is how foldr works. Every element of the list starting with the rightmost is passed as an argument to the accumulator function together with the value accumulated so far (for which you must provide an initial value). Now, the implementation. We have seen, that we want to get hold of the very first value that comes from the list and ignore everything else that comes after it. acc :: a -> Maybe a -> Maybe a # This is the function's type signature acc x Nothing = Just x # We wrap the first value ... acc x (Just y) = Just y # and keep hold of it When we now use this accumulator in our fold, it gets first called with arguments `3` and `Nothing` so the first pattern matches. Variable x is assigned the value `3` and the result is `Just 3`. The function gets called again with the second value `2` and `Just 3`, the result from the first call. This time, the first pattern does not match (Nothing does not match `Just 3`), but the second does. `x` is assigned the value `2`, `y` is assigned the value `3` (the one wrapped in the `Just`) and the result is `Just 3`. Same for the last element. Here is the complete implementation: last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc x (Just y) = Just y Or better last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x Nothing = Just x acc _ j = j Or even (this one will be harder to figure out) last5 :: [a] -> Maybe a last5 = foldr acc Nothing where acc x = maybe (Just x) Just Cheers, Stefan On Mon, Nov 10, 2014 at 06:28:46PM +0100, Roelof Wobben wrote:
oke, I try it with this : acc :: a -> Maybe a -> Maybe a acc a acc = if null a then Nothing else if (null (tail a)) then (Just acc) else acc a acc else if the tail a is empty so there is only 1 item then the output must be acc else must be run again ( there is a list with more then 1 item) but now I see this error message : Couldn't match expected type ‘a -> Maybe a -> Maybe a’ with actual type ‘Maybe a’ Relevant bindings include acc :: Maybe a and that is on the else part Roelof Benjamin Edwards schreef op 10-11-2014 18:07:
It is complining but as soon as I want to run it , I see this message : Non-exhaustive patterns in function acc
Yep, Maybe has two constructors, and you are only handling one. You should handle the Nothing case as well.
_______________________________________________ Beginners mailing list [1]Beginners@haskell.org [2]http://www.haskell.org/mailman/listinfo/beginners
References
1. mailto:Beginners@haskell.org 2. http://www.haskell.org/mailman/listinfo/beginners
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners