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
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/