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- -- Beauty of style and harmony and grace and good rhythm depend on simplicity. - Plato
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/
Joel,
I can think of a variety of ways to put a value at the end of a list of the same type. [...] 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).
Appending to a normal list is inherently messy and expensive. If it's doesn't have to be a normal list, though, things can get better. Look into "difference lists" as one example. Append for cheap while building, then get a list for linear-time cost when you're finished. The best data structure depends on what you need it to do. That said, your "obvious brute force" is the best of the ones you wrote, specifically because it's "obvious". It's clear what it does, it reuses existing functions well, and it's at least roughly as good as the others. John
participants (3)
-
Ertugrul Soeylemez -
Joel Neely -
John Dorsey