Have not got the time to read this but. Let me guess. Another programmer in a functional programming language realizing that the state is all over the place and gets copied around but still is so importantly immutable.
Two Vexing Problems in Functional Programming
41–50 of 217 posts
Re: Two Vexing Problems in Functional Programming
#42So, as the trend of forcing functional programming into imperative languages continues on its inexorable path, I just can't help but bring the old joke to mind more and more often: "Doctor, it hurts when I do this." "Well, then, don't do that." You mean, jamming a foreign paradigm into a language, where the advantages of the foreign paradigm are reduced and the disadvantages greatly magnified, hurts sometimes? Have y…
There's genuinely good things that came from FP that creeped into popular languages: * Algebraic data types * Pattern matching (with exhaustiveness) * Lambdas / Closures * Type inference
I don't believe it's true that algebraic data types "came from" FP. The name did, but the concept has existed since before high level languages existed. Actually before computers existed since it's in Type Theory. And before that it's in ordinary human thinking for thousands of years.
Re: Two Vexing Problems in Functional Programming
#43I've been coding in functional languages for 10 years, and they have problems, but these are not them. The first problem is solved in every functional language I've used (clojure, F#, OCaml) by immutable data structures (aka purely functional data structures, which is also the name of the de facto book on the topic, which is excellent but also you don't need to know any of this to use them. [1]). I'm surprised to see…
I love the Purely Functional Data Structures book (so many cool data structures and ideas!) but does really "solve" it? For e.g. I double checked and the PFDS for an array (the author's example) would be a skew-binary random access list with O(log N) cost for random access, whereas an "imperative random access array" is O(1). Of course, the skew-binary random access list has persistence (you get to keep references to…
Yes and no.
Ultimately, is the Big O scale going to be larger for certain cases? Yes. Is it going to matter? Maybe. Maybe not. The point the original comment is making is that the author seems unaware these data structures even exist; the fact he was having O(n) operations and found them to be too slow tells us nothing about the reasonableness of the O(logn) option for his use case. He mentioned using a 30k byte array; that's the difference between 30k operations, and 15. Cutting it from 15 to 1 is probably not going to be that meaningful; certainly not compared with the first jump.
Re: Two Vexing Problems in Functional Programming
#44You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole. The approaches & data structures aren't always the same. In my experience with FP you start with more of a top down approach in contrast to the bottom up approach discussed in the blog post. There are many good resources on this. I've referenced a few below. Of course there are many more. [1…
> You should not approach problems in functional languages with imperative techniques. It's fitting a square peg in a round hole.
This might be part of the problem with FP. Every popular CPU architecture is imperative.
Re: Two Vexing Problems in Functional Programming
#45I've been coding in functional languages for 10 years, and they have problems, but these are not them. The first problem is solved in every functional language I've used (clojure, F#, OCaml) by immutable data structures (aka purely functional data structures, which is also the name of the de facto book on the topic, which is excellent but also you don't need to know any of this to use them. [1]). I'm surprised to see…
I love the Purely Functional Data Structures book (so many cool data structures and ideas!) but does really "solve" it? For e.g. I double checked and the PFDS for an array (the author's example) would be a skew-binary random access list with O(log N) cost for random access, whereas an "imperative random access array" is O(1). Of course, the skew-binary random access list has persistence (you get to keep references to…
There are cost tradeoffs involved so you have to determine based on your application whether they solve the problem or not.
In a case like this you have several options:
1. Stick with mutation, reuse the original array and don't worry about being purely functional. This will probably be the optimal solution (vice explicitly creating a copy and mutating just the relevant bit). However, if you need the original for some reason then this is a non-solution.
2. Imitate the purely functional style with explicit copies, and accept the massive memory and performance costs that carries. You get to keep the cheaper read cost.
3. Use a better data structure, but losing (in particular) read performance, but largely mitigating the creation and "mutation" costs. (in quotes because the original is, from the perspective of the user, unchanged.)
Assuming you're in a language that doesn't provide (3) for free, and that (1) is a non-solution, you need to profile your system to decide between which of (2) and (3) is appropriate. With a large enough data structure or frequent enough updates, (3) is probably what you will want. If your data structure is small or updates are rare, then you can stick with (2). And if you have no idea which one will occur in the real-world (some users tend towards (2) being better and others towards (3)) you have to make an explicit choice on which one to provide better performance for.
Re: Two Vexing Problems in Functional Programming
#46Earlier quoted context omitted.
You mean, Haskell developers ditch the functional idiom and use a more imperative one when they need it for performance? And yes, they do, and it works nicely. But it's not solving any problem with the functional paradigm. Anyway, none of them is a problem with the semantics of FP. They are a problem of insufficient optimization. So they will probably get solved at some point.
ST is not 'imperative'. The monadic interface can look imperative sure, but then you can also use Applicative and friends and that's back to being functional. Of course, I prefer to think of what you call 'imperative' programming as function composition where >>= is the reverse of the 'normal' composition operator. Indeed, sequential imperative commands and function composition are isomorphic.
Hum... You declare an state and go modifying it with an action after another. Looks quite imperative to me. The fact that it returns an interpreter instead of values is meaningless if it doesn't change the way you think about the program.
If you personally prefers to read it as the declaration of a program that given an state modifies it step by step, you can claim it's functional. But you are alone on that, the language even has specialized syntax to push people into reading the former, and anything minimally complex all but requires it.
Re: Two Vexing Problems in Functional Programming
#47Earlier quoted context omitted.
I love the Purely Functional Data Structures book (so many cool data structures and ideas!) but does really "solve" it? For e.g. I double checked and the PFDS for an array (the author's example) would be a skew-binary random access list with O(log N) cost for random access, whereas an "imperative random access array" is O(1). Of course, the skew-binary random access list has persistence (you get to keep references to…
Yes and no. Ultimately, is the Big O scale going to be larger for certain cases? Yes. Is it going to matter? Maybe. Maybe not. The point the original comment is making is that the author seems unaware these data structures even exist; the fact he was having O(n) operations and found them to be too slow tells us nothing about the reasonableness of the O(logn) option for his use case. He mentioned using a 30k byte arra…
That's a good point.
I wonder if the problem is that efficient persistent arrays aren't in racket's standard library (there are some third-party libraries implementing them though). Since racket isn't a "pure FP" language, they include cons-arrays and mutable vectors, and I imagine they felt that there wasn't a need to include efficient persistent arrays in addition to those.
Re: Two Vexing Problems in Functional Programming
#48> Consistent with my loyalty to the functional-programming idiom, I designed my initial bf implementation so that each instruction would copy the existing bytes into a new array, change the byte of interest, return this new byte array, and abandon the old array (which would eventually be garbage-collected).
This would be a fun task to attempt with the new linear features of Haskell https://hackage.haskell.org/package/linear-base-0.1.0/docs/D...
Re: Two Vexing Problems in Functional Programming
#49Earlier quoted context omitted.
Yes, and also not a data structure that is suitable for the task. If you want to keep every version of the buffer as a value (which has nice properties like versioning) you would need a data structure that shares most of its structure with the previous versions. Like a persistent radix-n tree. Slower than mutable buffer for sure, but not pathological.
Got it. I'm familiar with persistent data structures but I was more curious as to the "Haskell approach" of doing the same problem (which, I assume, doesn't use persistent data structures per se). Follow-up question: if you wanted to implement the interpreter (as in the author's article) in idiomatic Haskell, would using the State monad be one solution? (I assume that's what you meant by "compose functions that manip…
Not sure there's any benefit in using the state monad for an interpreter.
My first thought is to model a cycle of the interpreter as a function of old state into new state.
I guess the state monad could be used to thread the state dataflow through the interpreter, but it would not make the copy-big-buffer any more efficient. Code using the state monad is still pure and uses immutable data.
Now if you have to use a mutable buffer (only one fits in memory?) then you could use techniques like the IO monad to deal with it.
Disclaimer: Am more Clojure than Haskell person.
Re: Two Vexing Problems in Functional Programming
#50So, as the trend of forcing functional programming into imperative languages continues on its inexorable path, I just can't help but bring the old joke to mind more and more often: "Doctor, it hurts when I do this." "Well, then, don't do that." You mean, jamming a foreign paradigm into a language, where the advantages of the foreign paradigm are reduced and the disadvantages greatly magnified, hurts sometimes? Have y…
The question I am left with, as someone who has a bit of experience with functional languages but much more in imperative/OOP languages, is does it ever make sense to develop something like the GUI applications the author was talking about using a primarily functional paradigm ? Assume you get to pick whatever FP language you want so the issue here isn't with shoehorning FP techniques into a language that doesn't sup…
That is a very good question. The discussion often circles around pro- and against FP. Proponents of "pure FP" seem to suggest that it is the best solution for everything always. Is it?
If not it would be nice to find discussion about when it is and when not and why? What is Haskell NOT the best solution for?