[Haskell-beginners] Re: question >>= [style, efficiency]

[Ertugrul Soeylemez]

Hello Joel,

any algorithm to append something to a list must have at least O(n)
complexity, where n is the length of the original list.  That said, the
third algorithm appears to be the best to me.  It has exactly O(n) and
is fully lazy, i.e. does not do anything at all until the list is
consumed up to the appendage.


Greets,
Ertugrul.


Joel Neely <joel.neely at gmail.com> wrote:

> I can think of a variety of ways to put a value at the end of a list
> of the same type.
> 
> -- cutesy-clever
> putAtEnd :: [a] -> a -> [a]
> putAtEnd xs x = reverse (x : reverse xs)
> 
> -- by hand
> atEnd :: [a] -> a -> [a]
> atEnd [] z = [z]
> atEnd (x:xs) z = x : atEnd xs z
> 
> -- obvious brute force
> infixr 9 +:
> (+:) :: [a] -> a -> [a]
> (+:) xs x = xs ++ [x]
> 
> I'd appreciate feedback/advice on whether:
> 1) I've missed any clearly-better alternatives;
> 2) any of those is obviously better or worse than the others;
> 3) I should have known where to look for the answer myself (instead of
> brute-force Googling).
> 
> I've semi-inadvertently mixed two issues above: infix-vs-prefix and
> algorithm design. TIA for suggestions on either.
> 
> -jn-
> 



-- 
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://blog.ertes.de/