3 ms·
That's something else entirely compared to tail call optimization, but yes some functional languages (e.g. Haskell) do this. I don't think F# does stream fusion
by jules 15y ago
That's something else entirely compared to tail call optimization, but yes some functional languages (e.g. Haskell) do this. I don't think F# does stream fusion though.
- loup-vaillant 15y agoI'd be surprised if the current implementation of F# didn't do anything of this sort. But as a language, I understand fusion is more difficult in ML than in Haskell: that's because ML is strict and non pure. Therefore, some of the assumptions you could do in a non-strict, pure language don't hold, and it may not be unconditionally true that ∀f, ∀g, map g ∘ map f == map (f ∘ g) because f or g could perform some side effect, or fail to terminate. (My example may be bogus, but I'm sure we can find some real one.)
- eru 15y agoFailure to terminate exists in Haskell, too.
- loup-vaillant 15y agoSure, but the order of evaluation do change something. For instance, infinite lists won't ever terminate, but taking the first 42 elements of an infinite list will terminate in Haskell, and not in ML. If you want to fuse the whole thing, it won't change the Haskell program, but it may change the ML one, by making it terminate an return the correct result! That's not an optimization any more, that's a language feature.
- eru 15y agoYes. Though the situation is only that rosy in Haskell under some circumstances. It's easy to get space leaks that make your program use O(run-time) memory, if you are not careful with the laziness.
- loup-vaillant 15y agoAgreed. My only point is that automatic fusion (stream, shortcut, and even inlining in general) "works" more often in a pure and lazy setting.