[Haskell-cafe] Naturality condition for inits

R J rj248842 at hotmail.com
Sat Mar 7 17:18:28 EST 2009

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

In case the definition of "inits" is relevant, my definition is:

inits                  :: [a] -> [[a]]

inits xs               =  [take n xs | n <- seglengths]


                              seglengths = [0..length xs]


Windows Live™: Life without walls.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090307/76e7d3c5/attachment.htm

More information about the Haskell-Cafe mailing list