Hi,
*last* :: [a] -> a last xs = head $ foldr f [] xs where f :: a -> [a] -> [a] f x [] = [x] f x ys = ys ++ [x]
a) in the second branch of f, you don't actually need to concatenate,
f x [] = [x] f _ ys = ys
works too, but is faster.
Why is it faster? I thought that the laziness would cause the concatenation not to be evaluated at all since we are taking the head of the list. Is that not the case? Thanks, Patrick
b) you can get much faster by delaying the pattern match,
f x ys = (case ys of { [] -> x; y:_ -> y }) : []
*init* :: [a] -> [a] init xs = tail $ foldr f [] xs where f :: a -> [a] -> [a] f x [] = [x] f x (y:xs) = y : x : xs
Correct too, but again not very efficient since it has to find the last element and bubble it to the front.
Much faster:
import Data.Maybe (fromMaybe)
init' :: [a] -> [a] init' = fromMaybe (error "init': empty list") . foldr f Nothing where f x mb = Just $ case mb of Just xs -> x:xs Nothing -> []
By delaying the pattern match on the Maybe until after the constructor is applied, we can start building the output with minimal delay (we only need to look whether there's a next list element to decide whether to cons it to the front or not).
Now, these seemed to be hard questions. So, I have three questions: (1) are these correct? They work on test cases, and I *did* do some quick proofs. They seem okay.
They are correct for finite lists, unzip and init above won't return on infinite lists (last shouldn't, so that's correct for infinite lists too). They are not, strictly speaking, correct for infinite lists. But that is way beyond beginner territory :)
(2) Is there a way to eliminate the post-processing of the lists (i.e., *head* in *last* and *tail* in *init*)?
Not in a clean way.
Let us consider last first.
Suppose we had
last xs = foldr f z xs
without post-processing. Since foldr f z [] = z and last [] = error "Prelude.last: empty list", we must have z = error "...". Now last (... x:[]) = x and foldr f z (... x:[]) = ... (f x z)
So f x y = y if y is not error "..." and f x (error "...") = x, that means f would have to find out whether its second argument is a specific error and return its first argument in that case, otherwise its second argument. It's possible to do that, but very unclean.
For init, the situation is similar, the value for the empty list case supplied to foldr must be an error and the combining function needs to know whether its second argument is an error and do things accordingly.
(3) Why the complex answers in the list archives? Am I missing something?
Don't know. In part, because beginners didn't find the easiest ways, I suppose, in part because it's not too easy to give efficient implementations with foldr.
_______________________________________________ Beginners mailing list Beginners@haskell.org http://www.haskell.org/mailman/listinfo/beginners
-- ===================== Patrick LeBoutillier Rosemère, Québec, Canada