[Haskell-cafe] 'Associative' order of calling
Janis Voigtländer
janis.voigtlaender at gmail.com
Sun Oct 25 05:58:23 UTC 2015
I don't think I see what you are getting at, Tom. Let's consider the
special case of non-empty lists. One fold-like function that has the
property I think Charles meant by 3., would be one that works as follows:
foldBalanced :: (a -> a -> a) -> [a] -> a
foldBalanced f [x] = x
foldBalanced f [x,y] = f x y
foldBalanced f [x,y,z] = f x (f y z)
foldBalanced f [x,y,z,u] = f (f x y) (f z u)
... -- I hope you can see the pattern (building f-application trees that
are as balanced as possible)
I don't see how this function can be written as g . foldl f z for some g
and z.
2015-10-25 0:55 GMT+02:00 Tom Ellis <
tom-lists-haskell-cafe-2013 at jaguarpaw.co.uk>:
> On Sat, Oct 24, 2015 at 08:12:11PM +0200, Janis Voigtländer wrote:
> > It has already been established in this thread what Charles meant by 3.
> >
> > He meant that a fold-function that has the property he is after would
> > guarantee that it:
> >
> > a) takes all the content elements from a data structure, say x1,...,xn,
> >
> > b) builds an application tree with the to-be-folded, binary operation f
> in
> > the internal nodes of a binary tree, whose leafs, read from left to
> right,
> > form exactly the sequence x1,...,xn,
> >
> > c) evaluates that application tree.
> >
> > Do you agree that what I describe above is a property of a given
> fold-like
> > function, not of the f handed to that fold-like function?
> >
> > And do you agree that what I describe above is a property that is weaker
> > than (and so, in particular different from) for example the property
> "this
> > fold-like function is foldl or foldr".
>
> I do agree. I would be interested whether you think such a property could
> differ from my earlier proposed property:
>
> "the function factors through `foldl f`", i.e. is `g . foldl f` for
> some `g`.
>
> (Actually when I wrote that I suppose I meant `g . foldl f z` for some `g`
> and `z`)
>
> Tom
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/haskell-cafe/attachments/20151025/35827bbd/attachment.html>
More information about the Haskell-Cafe
mailing list