[Haskell-beginners] Thompson Exercise 9.13

[Patrick LeBoutillier]

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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>



-- 
=====================
Patrick LeBoutillier
Rosemère, Québec, Canada