Dan Weston westondan at imageworks.com
Wed Mar 25 15:40:08 EDT 2009

```So to be clear with the terminology:

inductive   = good consumer?
coinductive = good producer?

So fusion should be possible (automatically? or do I need a GHC rule?) with
inductive . coinductive

Or have I bungled it?

Dan

wren ng thornton wrote:
> Thomas Hartman wrote:
>> sorry, wrong function.
>>
>> should be
>>
>> partitions [] xs = []
>> partitions (n:parts) xs =
>>   let (beg,end) = splitAt n xs
>>   in beg : ( case end of
>>                [] -> []
>>                xs -> partitions parts xs)
>
>
> It's not tail recursive, FWIW. The recursive expression has (:) as it's
> head before it hits `partitions`. It is however nicely coinductive,
> which has other good properties.
>
> We could make it tail-recursive easily,
>
>    partitions = go id
>        where
>        go k []     xs = k []
>        go k (n:ns) xs =
>            let (beg,end) = splitAt n xs
>                k'        = k . (beg:)
>            in  case end of
>                []  -> k' []
>                xs' -> go k' ns xs'
>
> (Note how this version has `go` as the head of the recursive expression.)
>
> ...however this version has different strictness properties. In
> particular, let both input lists be infinite (and take a finite portion
> of the result). The original version works fine because it gives a
> little bit of output (beg:) at each step of the recursion ---which is
> all "coinductive" means. The tail-recursive version hits _|_ however,
> because we've delayed giving any input (k []) until one of the two lists
> hits [] ---we've tried doing induction on co-data and so we hit an
> infinite loop.
>
> This dichotomy between coinduction and tail-recursion is quite common.
> It's another example of the recently discussed problem of defining foldr
> in terms of foldl. Whether the termination differences matter depends on
> how the function is to be used.
>
>
> Another nice property of coinduction is that it means we can do
> build/fold fusion easily:
>
>    partitions = \ns xs -> build (\cons nil -> go cons nil ns xs)
>        where
>        go cons nil = go'
>            where
>            go' []     xs = nil
>            go' (n:ns) xs =
>                 let (beg,end) = splitAt n xs
>                 in  beg `cons` case end of
>                                []  -> nil
>                                xs' -> go' ns xs'
>
> By using the GHC.Exts.build wrapper the fusion rules will automatically
> apply. The second wrapper, go, is just so that the worker, go', doesn't
> need to pass cons and nil down through the recursion.
>

```