Joachim Breitner | 6 Dec 18:51 2013
Picon

Higher order functions and strictness

Hi,

we currently have a pattern where a higher order function (like foldl,
or Map.unionWith), which naively build thunks without the passed
function having a chance to prevent that. Therefore, there are variants
like foldl', which seq the result of the function.

Can one have one function that allows for both? I take
        mapMaybe :: (a -> b) -> Maybe a -> Maybe b
as an (simple, and not very relevant) example. With that signature,
there is not much "mapMaybe f x" can do. It either applies f lazily to
x, or strictly.

One could have
        data Box a = Box a
        mapMaybe :: (a -> Box b) -> Maybe a -> Maybe b
and have mapMaybe pattern-match on Box. Then it will evaluate
_something_ of the return value of f, and f can have control over
whether the thing inside the box is evaluated or not. So this is nice,
but unfortunately we now allocate and destruct a box that we do not care
about.

But since I had been looking at some unboxed tuples recently, I noticed
that the singleton unboxed tuple allows for exactly that: Call a
function in a way that it has control (i.e. can force stuff), but do not
necessarily evaluate its result, and all that without extra allocations.

Here is some example code:

        {-# LANGUAGE UnboxedTuples #-}
(Continue reading)

Tom Ellis | 6 Dec 21:52 2013
Picon

Re: Higher order functions and strictness

On Fri, Dec 06, 2013 at 05:51:03PM +0000, Joachim Breitner wrote:
> But since I had been looking at some unboxed tuples recently, I noticed
> that the singleton unboxed tuple allows for exactly that: Call a
> function in a way that it has control (i.e. can force stuff), but do not
> necessarily evaluate its result, and all that without extra allocations.

This is a very, very neat observation!  It seems that the unboxed singleton
allows fine grained control over order of evaluation without imposing any
datastructure overhead.  I am (very slowly) working on an alternative
type-system for GHC which will make it look like a strict language with
explicit thunk datatype (although it will still be good old GHC under the
hood).  Your observation will be helpful for performance.

> Of course (#..#) has it downsides, e.g. you cannot make a newtype for it
> (newtype Box a = (# x #)) does not work... 

This is a shame, although it seems like in principle it may be possible

    https://ghc.haskell.org/trac/ghc/ticket/1311

Still if SPJ's 'brain is too small to figure out all the ramifications of
dropping the "newtypes are always boxed" assumption' then I don't hold out
much hope that /anyone/ will be able to do anything about this restriction :)

Tom

Gmane