Am Samstag, 7. März 2009 23:18 schrieb R J:
Here's another Bird problem that's stymied me:
The function "inits" computes the list of initial segments of a list; its type is inits :: [a] -> [[a]]. What is the appropriate naturality condition for "inits"?
The only discussion in the text concerning naturality conditions concerns map, where the naturality conditions are stated in what seem to be quasi-commutativity laws over the composition operator, as follows:
f . head = head . map f, where f is strict (i.e., f _|_ = _|_) map f . tail = tail . map f map f (xs ++ ys) = map f xs ++ map f ys map f . reverse = reverse . map f map f . concat = concat . map (map f)
I believe that none of the following naturality conditions, extrapolated from those above, hold:
a. head . inits = inits [head] b. tail . inits = inits . tail c. reverse . inits = inits . reverse d. concat . inits = inits . concat
How does inits interplay with (map f)? Though inits . tail =/= tail . inits, there is an interesting relation between inits (tail xs) and inits xs, which? When you also consider the function tails, there is an interesting relation involving inits and reverse, too.
In case the definition of "inits" is relevant, my definition is:
inits :: [a] -> [[a]]
inits xs = [take n xs | n <- seglengths]
where
seglengths = [0..length xs]
Better define it recursively. inits [] = [[]] inits (x:xs) = []:map (x:) (inits xs)
Thanks.