4 ms·

> You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "s

> You can reason about code even if you think that any program is a sequence of operations, but you can do it better, if your idea of program is wider than a "series of operations in a specific order". Can you provide a concrete example of this? Otherwise it is just a hand wavy thing to say (which are way too many in programming world).

ordu 8y ago
I'm not sure that example can possible work here. The best example would be something that is impossible to reason about in imperative terms but possible in functional terms. So... we need sufficiently difficult task, that will cause problems with understanding. And this task should be easy enough to be an example to write in HN comment. A contraversial setup, isnt it? I should use an artifical task as an example, but the trouble is if someone thinks in imperative terms only, then when he tried to think about a task he would frame the task in imperative terms and he would see it as an imperative problem and would fail to see it as a functional one. It is not because he is stupid or he posess some other disabilities, it is just the way human mind works. It is like people saying "what is so good about language X, if you can do all in Y"? "Why one needs OOP languages, if you can do OOP in C?" The way we think about problems defines how we see problems, and what we see as a problems. But let us try. qsort [] = [] qsort (x:xs) = qsort [ y | y <- xs, y < x ] ++ [x] ++ qsort [ y | y <- xs, y > x ] This is functional definition of a quicksort. It is possible the worst definition from performance standpoint, but I like it for clarity of algorithm expression, and it demonstrates the point. I remember the very first time I saw quicksort in C I have spent maybe half an hour trying to figure out how that code was supposed to work. Here you can see compressed version which have nothing but the very idea of quicksort: quicksort of empty sequence is an empty sequence. quicksort of sequence starting with x is a concatenation (operator ++) of three lists: quicksorted list of items from the rest of sequence (sequence without the first element which is designated as x) that are lesser then x, list of one element x, and quicksorted list of elements that are greater than x. Of course, if you want quicksort to be sorting in place, you would need to think about small details like traversing two pointers, one from the front of the sequence, second from the back, swapping elements, and not forgetting about the choosen one... Yeah, reality is more complicated than that, sometimes you cannot get rid of complexity. Functional compilers are constantly searching for optimizing techniques to get rid of all these small details, and in some ways they are succeeding. Though no one is good enough to generate machine code for sorting in place by compiling high level code above. But I tried to demonstrate the idea of abstraction of details and how it helps to understand code and to reason about it, and I believe the example is showing it.
- ankurdhama 8y ago
  My question was about "sequence of things to do", which is different concept than "imperative programming". Sequence means A should happen before B and this is something that you will have to keep in mind and then encode in the target language. For example: in C language A could be a statement that modify some data and B could be another statement that uses the updated data. In Haskell A could be an expression that produce a value and that value is used in expression B. In both cases A have to be "done" before B and you need to keep this in mind while writing the code. As far as imperative vs functional goes: Remove the assignment operator from an imperative language and you will end up with functional language without bell and whistles (then you will have to make conditionals as expressions and instead of loops you will need to use recursion).
  - ordu 8y ago
    > In Haskell A could be an expression that produce a value and that value is used in expression B. In both cases A have to be "done" before B and you need to keep this in mind while writing the code. Yes, and no. For example B(A(x)), haskell can call A(x), get result, then call B passing result as argument. Or it can call B, passing closure as argument, and when it comes to a point, when calculation of B cannot be continued if we do not know value of A(x) only then A(x) would be calculated. In some sense A(x) was done before B -- before B was finished, but from other hand calculation of A(x) was started after starting calculation of B. > My question was about "sequence of things to do", which is different concept than "imperative programming". I'm not sure, that I can see a difference, but nevertheless, in example above there is not sequence of operations. There is almost declarative definition of a quicksorted list. There are multiple ways to linearize it into sequence of operations and even if there was single way I don't mind. It is the task of a compilator to make this linearization, not mine.

ordu 8y ago

I'm not sure that example can possible work here. The best example would be something that is impossible to reason about in imperative terms but possible in functional terms. So... we need sufficiently difficult task, that will cause problems with understanding. And this task should be easy enough to be an example to write in HN comment. A contraversial setup, isnt it? I should use an artifical task as an example, but the trouble is if someone thinks in imperative terms only, then when he tried to think about a task he would frame the task in imperative terms and he would see it as an imperative problem and would fail to see it as a functional one. It is not because he is stupid or he posess some other disabilities, it is just the way human mind works. It is like people saying "what is so good about language X, if you can do all in Y"? "Why one needs OOP languages, if you can do OOP in C?" The way we think about problems defines how we see problems, and what we see as a problems. But let us try. qsort [] = [] qsort (x:xs) = qsort [ y | y <- xs, y < x ] ++ [x] ++ qsort [ y | y <- xs, y > x ] This is functional definition of a quicksort. It is possible the worst definition from performance standpoint, but I like it for clarity of algorithm expression, and it demonstrates the point. I remember the very first time I saw quicksort in C I have spent maybe half an hour trying to figure out how that code was supposed to work. Here you can see compressed version which have nothing but the very idea of quicksort: quicksort of empty sequence is an empty sequence. quicksort of sequence starting with x is a concatenation (operator ++) of three lists: quicksorted list of items from the rest of sequence (sequence without the first element which is designated as x) that are lesser then x, list of one element x, and quicksorted list of elements that are greater than x. Of course, if you want quicksort to be sorting in place, you would need to think about small details like traversing two pointers, one from the front of the sequence, second from the back, swapping elements, and not forgetting about the choosen one... Yeah, reality is more complicated than that, sometimes you cannot get rid of complexity. Functional compilers are constantly searching for optimizing techniques to get rid of all these small details, and in some ways they are succeeding. Though no one is good enough to generate machine code for sorting in place by compiling high level code above. But I tried to demonstrate the idea of abstraction of details and how it helps to understand code and to reason about it, and I believe the example is showing it.

ankurdhama 8y ago
My question was about "sequence of things to do", which is different concept than "imperative programming". Sequence means A should happen before B and this is something that you will have to keep in mind and then encode in the target language. For example: in C language A could be a statement that modify some data and B could be another statement that uses the updated data. In Haskell A could be an expression that produce a value and that value is used in expression B. In both cases A have to be "done" before B and you need to keep this in mind while writing the code. As far as imperative vs functional goes: Remove the assignment operator from an imperative language and you will end up with functional language without bell and whistles (then you will have to make conditionals as expressions and instead of loops you will need to use recursion).
- ordu 8y ago
  > In Haskell A could be an expression that produce a value and that value is used in expression B. In both cases A have to be "done" before B and you need to keep this in mind while writing the code. Yes, and no. For example B(A(x)), haskell can call A(x), get result, then call B passing result as argument. Or it can call B, passing closure as argument, and when it comes to a point, when calculation of B cannot be continued if we do not know value of A(x) only then A(x) would be calculated. In some sense A(x) was done before B -- before B was finished, but from other hand calculation of A(x) was started after starting calculation of B. > My question was about "sequence of things to do", which is different concept than "imperative programming". I'm not sure, that I can see a difference, but nevertheless, in example above there is not sequence of operations. There is almost declarative definition of a quicksorted list. There are multiple ways to linearize it into sequence of operations and even if there was single way I don't mind. It is the task of a compilator to make this linearization, not mine.