[Haskell-cafe] Can I check the length in a guarded expresion

Richard A. O'Keefe ok at cs.otago.ac.nz
Mon Nov 10 03:40:12 UTC 2014


On 10/11/2014, at 8:07 am, Roelof Wobben <r.wobben at home.nl> wrote:

> Found it.
> 
> This is working ; 
> 
> last3::[a]-> Maybe a; 
> last3 a 
>   | null a = Nothing
>   | length a == 1 = Just (head a) 
>   | otherwise = last3 (tail a)

I believe it has already been mentioned,
but what you have here is an O(|a|**2) solution.

The way I’d write it is

    last4 :: [a] -> Maybe a

    last4 []     = Nothing
    last4 (x:xs) = Just $ loop x xs
      where loop x [] = x
            loop _ (y:ys) = loop y ys


In ghci,
*Main> :set +s

*Main> last3 [1..10000]
Just 10000
(0.14 secs, 13696656 bytes)
*Main> last4 [1..10000]
Just 10000
(0.00 secs, 3131552 bytes)

*Main> last3 [1..100000]
Just 100000
(11.92 secs, 33134136 bytes)
*Main> last4 [1..100000]
Just 100000
(0.02 secs, 15520360 bytes)

You really _don’t_ want to be calling length in a loop like that.

length a == 1 if and only if a == [_]

Using null, head, tail is not really the Haskell Way.

last3 []     = Nothing
last3 [x]    = Just x
last3 (_:xs) = last3 xs




More information about the Haskell-Cafe mailing list