Haskell: Pure and Lazy, yet Functional(updike.org)
updike.org
Haskell: Pure and Lazy, yet Functional
http://www.updike.org/articles/Pure_Lazy_Functional
4 comments
If you haven't tried it yet, Haskell is a real joy to use. There's a Batteries Included binary distribution http://hackage.haskell.org/platform/index.html , and a really good free online book for it http://book.realworldhaskell.org/
http://learnyouahaskell.com/
Worth a look, too.
Worth a look, too.
It allows you to divide the problem up into smaller conceptual units which get combined in an efficient way [2]. For example you can write your code in this clean (seemingly inefficient) style, where each piece does something self-contained to an entire list or string: (a) read an entire 1GB file, (b) split the file into a list of words (c) make a new list that has the word “the” filtered out, (d) append the words back together into a string (e) write the whole string to a file.
The compiler, however, glues this all together as if you had written a single chunk of code that (a) reads single characters from the 1GB file until (b) you have a full word (c) throwing out the word “the” in the process, (d/e) and then writing each letter of the current word to the file. Notice how this “single chunk” style never reads in the entire file, only enough to look at a word or character at a time (or maybe 1k chunks if you have buffering set, for efficiency)! Also notice how an ordinary “single-chunk” style of programming would not allow you to split up each of the subtasks (a-e) into totally separate functions [3] that you can use elsewhere in your program: they are stuck directly inside your while or for loop! One of the only (and bad) ways to get around this in C++, for example, is with macros (Or write your own lazy streams/lazy strings library). This one is a bit subtle.
Sigh. You are about to get flamed, you poor naive fool. Never, ever direct an attack towards C++, especially when you don't know what you're talking about. This is what iterators do in C++. You can write objects which are called over something that allows iteration, and they can be inlined together. So you end up with a single iteration over a collection, with minimal intermediary data structures, but modeled in convenient discrete steps. Also worth noting is that this has nothing to do with laziness at all. In fact most powerful languages allow for something like this, going all the back to at least APL.
You can use iterators to solve this, and indeed this is why all these imperative/object-oriented languages have had to add iterators to the language: to allow you to write code that doesn’t evaluate everything too soon, to be more lazy. The cost of iterators (at least to me) is you actually have to change gears mentally and syntactically. You now have to (a) know the syntax (which varies from language to language) and (b) make some kind of class with some methods, write all these little bits of code, and of course, if you never reuse the code, it was a complete waste, you should have just coded it directly into your loop.
Er, iterators are reusable. As reusable as functions intended for fmap in Haskell are, generally.
By the way, with your 1gb file example, you would not do this with regular recursion or folds over lists in Haskell, since space usage will explode during your intermediary list allocations. You need to use iteratees or some other way that gives determinate space usage. An explicit recursion from the right or a normal fold will kill you.
Haskell is even more weird than all these other languages because it is “purely functional”. That means you cannot mutate variables or introduce “side effects” anywhere in your program (short of I/O). This is good and bad. One of the major benefits is that you never have those bugs when some code changes something in place over here in your program and you don’t notice it until it breaks something way over there. In addition, the compiler is guaranteed certain things about each function and can perform certain optimizations at compile time. The bad part is that there are certain things that are more natural or more efficient just to “vary” variables in place, like the computer hardware does underneath.
You probably should have mentioned purity before laziness, because you would have a really difficult time creating a lazy language that wasn't pure. Anyway, in Haskell, you can use the ST (or IO) monad to do efficient, safe, pure in-place mutations.
If you write “a = 4” then you cannot later say, “a = 5”
The hardest thing about learning Haskell is perspective. There is an old saying that goes something like "Any FORTRAN programmer worth his salt can write FORTRAN programs in any language." But one thing they got right when they designed the language is that it is so different that you can only program in it ‘in Haskell,” thinking in Haskell. Your program won’t work unless you understand Haskell. The old ways of writing programs (C/C++/Java/Perl/FORTRAN) don’t work in Haskell.
Sure you can. Just do everything in the State, ST or IO monads. In fact, Haskell makes for quite a nice and elegant imperative language, used correctly. If it's Turing-complete, it's FORTRAN complete.
Haskell is cool, and I'm glad the author of this article is liking it so far. But I encourage people to hold their tongues until they know more about which they speak. Misguided advocacy will just bring on flames. None of the examples provided help any arguments he tries to make, which generally seem to be mistaken. I do not think he really understands laziness yet; none of what he wrote really has anything to do with laziness (except not needing a special form for conditionals). I did not understand laziness at first, either (and feel like I still don't!) so I hope he will retract this article before it brings on the legions of programmers from other languages capable of deftly defeating all of his examples in their own language of choice.
I encourage everyone to learn more about Haskell, but there are many pieces by many other authors of a very high caliber. There are lots of great learning resources now, and all of the tools to learn yourself install readily on all major platforms.
The compiler, however, glues this all together as if you had written a single chunk of code that (a) reads single characters from the 1GB file until (b) you have a full word (c) throwing out the word “the” in the process, (d/e) and then writing each letter of the current word to the file. Notice how this “single chunk” style never reads in the entire file, only enough to look at a word or character at a time (or maybe 1k chunks if you have buffering set, for efficiency)! Also notice how an ordinary “single-chunk” style of programming would not allow you to split up each of the subtasks (a-e) into totally separate functions [3] that you can use elsewhere in your program: they are stuck directly inside your while or for loop! One of the only (and bad) ways to get around this in C++, for example, is with macros (Or write your own lazy streams/lazy strings library). This one is a bit subtle.
Sigh. You are about to get flamed, you poor naive fool. Never, ever direct an attack towards C++, especially when you don't know what you're talking about. This is what iterators do in C++. You can write objects which are called over something that allows iteration, and they can be inlined together. So you end up with a single iteration over a collection, with minimal intermediary data structures, but modeled in convenient discrete steps. Also worth noting is that this has nothing to do with laziness at all. In fact most powerful languages allow for something like this, going all the back to at least APL.
You can use iterators to solve this, and indeed this is why all these imperative/object-oriented languages have had to add iterators to the language: to allow you to write code that doesn’t evaluate everything too soon, to be more lazy. The cost of iterators (at least to me) is you actually have to change gears mentally and syntactically. You now have to (a) know the syntax (which varies from language to language) and (b) make some kind of class with some methods, write all these little bits of code, and of course, if you never reuse the code, it was a complete waste, you should have just coded it directly into your loop.
Er, iterators are reusable. As reusable as functions intended for fmap in Haskell are, generally.
By the way, with your 1gb file example, you would not do this with regular recursion or folds over lists in Haskell, since space usage will explode during your intermediary list allocations. You need to use iteratees or some other way that gives determinate space usage. An explicit recursion from the right or a normal fold will kill you.
Haskell is even more weird than all these other languages because it is “purely functional”. That means you cannot mutate variables or introduce “side effects” anywhere in your program (short of I/O). This is good and bad. One of the major benefits is that you never have those bugs when some code changes something in place over here in your program and you don’t notice it until it breaks something way over there. In addition, the compiler is guaranteed certain things about each function and can perform certain optimizations at compile time. The bad part is that there are certain things that are more natural or more efficient just to “vary” variables in place, like the computer hardware does underneath.
You probably should have mentioned purity before laziness, because you would have a really difficult time creating a lazy language that wasn't pure. Anyway, in Haskell, you can use the ST (or IO) monad to do efficient, safe, pure in-place mutations.
If you write “a = 4” then you cannot later say, “a = 5”
foo x = x + a
where a = 4
b = a + 2
where a = 5
do a <- readFile "foo.txt"
putStrLn a
a <- readfile "bar.txt"
putStrLn a
The hardest thing about learning Haskell is perspective. There is an old saying that goes something like "Any FORTRAN programmer worth his salt can write FORTRAN programs in any language." But one thing they got right when they designed the language is that it is so different that you can only program in it ‘in Haskell,” thinking in Haskell. Your program won’t work unless you understand Haskell. The old ways of writing programs (C/C++/Java/Perl/FORTRAN) don’t work in Haskell.
Sure you can. Just do everything in the State, ST or IO monads. In fact, Haskell makes for quite a nice and elegant imperative language, used correctly. If it's Turing-complete, it's FORTRAN complete.
Haskell is cool, and I'm glad the author of this article is liking it so far. But I encourage people to hold their tongues until they know more about which they speak. Misguided advocacy will just bring on flames. None of the examples provided help any arguments he tries to make, which generally seem to be mistaken. I do not think he really understands laziness yet; none of what he wrote really has anything to do with laziness (except not needing a special form for conditionals). I did not understand laziness at first, either (and feel like I still don't!) so I hope he will retract this article before it brings on the legions of programmers from other languages capable of deftly defeating all of his examples in their own language of choice.
I encourage everyone to learn more about Haskell, but there are many pieces by many other authors of a very high caliber. There are lots of great learning resources now, and all of the tools to learn yourself install readily on all major platforms.
Iterators sometimes require restructuring, as in
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
In Haskell they don't - you might write this "producer-consumer" composing a function that produces a stream with a function that consumes a stream. How would you approach that problem in C++?
http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
In Haskell they don't - you might write this "producer-consumer" composing a function that produces a stream with a function that consumes a stream. How would you approach that problem in C++?