[Haskell-cafe] Naturality condition for inits
Daniel Fischer
daniel.is.fischer at web.de
Sat Mar 7 17:46:51 EST 2009
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.
More information about the Haskell-Cafe
mailing list