[Haskell-beginners] pattern match vs. pure function

[Bastian Erdnüß]

On Oct 20, 2010, at 2:23, Daniel Fischer wrote:

> On Wednesday 20 October 2010 01:23:49, Bastian Erdnüß wrote:
>> Suppose I would want to write a function rmap that acts like
>> 
>> rmap [f,g,h] x == [f x, g x, h x]
>> 
>> Do I gain any advantage or disadvantage (beside readability) from using
>> 
>> rmap = flip $ map . flip id
>> 
>> over
>> 
>> rmap []     _ = []
>> rmap (f:fs) x = f x : rmap fs x
>> 
>> ?
>> 
>> I could imagine Haskell can optimize the first version better since it
>> refers to the built in map function.  But beside that, does Haskell
>> struggle with the combinatory stuff in the first version?  Or does it
>> get optimized away?
> 
> Well, you can ask GHC what it does with the definitions.
> Let's compile
> 
> module RMap where
> 
> rmap :: [a -> b] -> a -> [b]
> rmap = flip $ map . flip id
> 
> recmap :: [a -> b] -> a -> [b]
> recmap [] _     = []
> recmap (f:fs) x = f x : recmap fs x
> 
> and look at the generated Core (obtained via -ddump-simpl).

Cool.  Didn't know that.

> The @ x_yz things are type annotations, otherwise Core is pretty close to 
> Haskell. It takes a bit to get used to reading Core, but it's not that 
> difficult (as long as the functions are short).

I see.  Well, still better then my hand writing ;-)

> First, without optimisations:
>
> [some good explinations]

Thanks!

> Now with optimisations. [...]
> 
> There, that looks much better than before (and for short lists, it performs 
> much better, but for long lists, the difference should be negligible).
> flip, ($) and (.) have been inlined and eliminated, what we get is
> 
> rmap fs x = map (\f -> f x) fs
> 
> , which is really nice. In fact, it's even nicer than what we got for 
> recmap, because the compiler knows map, there are rewrite rules, which can 
> produce much better code when the function is used, for example, it's 
> possible that the list of functions is completely eliminated and a use is 
> rewritten to a direct loop instead of allocating a list cell for each 
> function in the list. And it can profit from the rule
> 
> map f . map g = map (f . g)
> 
> which is much harder to detect for the direct recursion.

Good news, seems like Haskell has no problem with combinators.  As I hoped I could expect.

>> And how "expensive" are pattern matches on the other side, anyway?
> 
> Depends on the pattern, of course. Matching "oh" against [] is much cheaper 
> than matching "This is an expensive car" against
> 
> 'T':'h':'i':'s':' ':'a':'n':' ':'e':'x':'p':'e':'n':'s':'i':'v':'e':' 
> ':'p':'a':'t':'t':'e':'r':'n':' ':'m':'a':'t':'c':'h':_
> 
> But generally, pattern matching is quite cheap. The (well, one) advantage 
> of higher order functions like map is that they're easier to optimise when 
> they're used, given that somebody has taught the compiler how.

I understand.

Many thanks again for pointing out how I can test such things myself with -ddump-simple.

Cheers,
Bastian