[Haskell-cafe] about Haskell code written to be "too smart"

[Dan Weston]

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.
>