The Strange Loop conference

[Peter Alexander]

On 21/09/11 8:29 PM, Timon Gehr wrote:
> Where D still loses when compared to Scala is functional code syntax:
>
> val newcol = collection filter {x=>x<5} map {x=>2*x}
>
> or maybe
>
> val newcol = for(x<-collection if(x<5)) yield 2*x
>
> vs
>
> auto newrange = filter!((x){return x<5;})(map!((x){return 2*x;})(range));

Of course, you could write:

auto newrange = filter!"a<5"(map!"2*a"(range));

At least I think that works??


> I believe that is part of the reason why it is less known. If I write
> functional style code in D I unfortunately usually get feedback that it
> is "extremely hard to read". Furthermore, Scala has built-in tuples, and
> eg delimited continuations, which enable some more functional
> programming idioms. std.algorithm/std.range are also considerably (and
> as I understand, deliberately) underpowered for FP when compared to eg
> Haskell's standard set of libraries, and writing a good range from
> scratch is usually a serious undertaking.

The problem it's simply intractable to do lazy computation in D while 
maintaining the 'correct' static typing.

For example, in Haskell, map (correctly) has the signature:

map :: (a -> b) -> [a] -> [b]

but in D, std.map has the signature (expressed in some Haskell/D pseudocode)

map :: (a -> b) -> [a] -> Map!((a -> b), [a])

To get the same kind of signature as Haskell, you'd need to use eager 
computation in D, but that's horrendously inefficient in most cases. 
Alternatively, you can use interfaces, but then you lose type 
information in a lot of situations.

The problem with the D situation is that if I have a function:

void foo(int[])

then it can't be called with:

foo(map!"2*a"([1, 2, 3]));

I'm forced to either:
(a) use eager computation by wrapping it in array(...)
(b) change foo to be a template

What if foo is a virtual member function? Those can't be templates.

What if foo recursively maps to itself? e.g.

auto foo(Range)(Range r)
{
     if (r.length == 1)
         return r.front;
     r.popFront();
     return map!"2*a"(r);
}

Someone in D.learn tried to write quickSort in a similar way, but it 
obviously doesn't work because of the infinite number of template 
instantiations. To simulate lazy computation in D, you require a type 
transformation, which doesn't work with recursion. You're only choice is 
to abstract away to some sort of IRange!T interface to remove the type 
divergence, but then you lose performance, and in some cases, type 
information.

Of course, if every function that accepts a range becomes a template 
then you have the practical problem of managing the number of template 
instantiations. Code bloat is still a real problem with heavy template 
usage.

Finally, map in Haskell just makes sense. You have a list of a's, a 
function of 'a to b' and you get a list of b's out the other end. It's 
simple, it's exactly what you want, and it just works. You can't say the 
same in D.

Of course, what D's lazy ranges do give you is performance in the simple 
cases*. There's no indirect function calls, which means things can be 
inlined, and you save yourself a few potential cache misses. We just 
have to accept that this performance is at the expense of simplicity and 
expressability.

* I say simple cases because Haskell compiler can do deforestation 
optimisations, which are essentially intractable in D due to its 
imperative roots.