[Haskell-cafe] Stupid newbie question

[Brian Hulley]

Brian Hulley wrote:
> Brian Hurt wrote:
>> nth 0 (x:xs) = Some x
>> nth i (x:xs) = if i < 0 then Empty else nth (i-1) xs
>> nth i [] = Empty
> [blows stack on large i]
>
> As other people have pointed out, this is due to laziness. I'd write
> it like:
>
>    nth 0 (x:_) = Some x
>    nth i (_:xs) = of i < 0 then Empty else (nth $! i-1) xs
                           ^^^ -- oops!

>    nth _ [] = Empty

I think the above code would be more efficient written as:

    nth n xs = if n < 0 then Empty else nth' n xs
        where
            nth' 0 (x:_) = Some x
            nth' i (_:xs) = (nth' $! i - 1) xs
            nth' _ _ = Empty

since the first 2 cases deal with every situation where we've got a 
non-empty list and an index >= 0 (so no need to keep checking that the index 
is >= 0 in the second case - instead the test can be moved outside the 
"loop") and there's no need to pattern match against [] in the last case 
because we already know this must be an empty list.
(Though in general it's probably a good idea to make each pattern as 
independent as possible when writing a function so that if some cases of a 
function are later edited there's more chance of the compiler being able to 
lead you to errors via the "incomplete patterns" warning - hopefully the 
compiler can optimize out any redundant checks)

Brian.
-- 
http://www.metamilk.com