On Mon, Apr 29, 2013 at 8:40 PM, Dan Doel <dan.d...@gmail.com> wrote:
> On Mon, Apr 29, 2013 at 10:05 AM, Duncan Coutts < > duncan.cou...@googlemail.com> wrote: > >> On Thu, 2013-04-25 at 00:52 +0200, Gábor Lehel wrote: >> > On Wed, Apr 24, 2013 at 7:56 PM, Bryan O'Sullivan <b...@serpentine.com >> >wrote: >> > >> > > On Wed, Apr 24, 2013 at 10:47 AM, Duncan Coutts < >> > > duncan.cou...@googlemail.com> wrote: >> > > >> > >> I address it briefly in my thesis [1], Section 4.8.2. I think it's a >> > >> fundamental limitation of stream fusion. >> > >> >> > > >> > > See also concat, where the naive fusion-based implementation has >> quadratic >> > > performance: >> > > >> > > concat :: [Text] -> Text >> > > concat txts = unstream (Stream.concat (List.map stream txts)) >> > > >> > > I've never figured out how to implement this with sensible >> characteristics >> > > within the fusion framework. >> > > >> > >> > If you could "solve" concat, might that also lead to be being able to do >> > without the Skip constructor? >> >> Dan is right, we still need Skip. My suggested "solution" to the >> concatmap problem is also mostly independent of the skip issue. >> >> You shouldn't think of skip as being a hack. It's not. It's how we >> express a more general class of producers in a way that is productive. > > > To further this, note that in a total language, with the type: > > codata Stream a = End | Yield a (Stream a) > > filter is not definable; it is not a total function. At least, barring an > extra proof of some sort that the predicate will yield true after a finite > amount of time. concat is similar. > > Also, adding Skip (Stream a) is a relatively standard way of explicitly > representing lazy, partial values. (This is opposed to the partiality > monad, which is like an encoding of strict general recursion). That is, if > νF is the type of total values, then ν(F + Id) is the type of partial > values. I don't know how easy it is to delete from a more complex tree > using just that extension, but in theory you could productively represent > arbitrary manipulations with just that, I believe. > > -- Dan > Very interesting (and makes sense), thank you. -- Your ship was destroyed in a monadic eruption.
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe