4 ms·

"Now pick the two lowest-level and most isolated functions in the entire codebase. They're used all over the place, but are never called from the same modules.

"Now pick the two lowest-level and most isolated functions in the entire codebase. They're used all over the place, but are never called from the same modules. Now make these dependent on each other: function A behaves differently depending on the number of times function B has been called and vice-versa." Why would anyone want to do this? This sounds like a really, really bad idea. I'm sure there are legitimate problems that are easier to solve with an imperative language than a functional one (such as quicksort, perhaps), but this article doesn't provide any.

yoklov 15y ago
Agreed, but just because: Quicksort in Haskell: quicksort [] = [] quicksort (x:xs) = quicksort front ++ [x] ++ quicksort behind where front = filter (<= x) xs behind = filter (> x) xs
- xyzzyz 15y ago
  I hate this example. This is not what quicksort is about. Quicksort is about sorting array in place. The preceding code is not. Also I can't see how it's relevant to the thread.
  - Confusion 15y ago
    Quicksort is the demonstration of the divide-and-conquer strategy, which is just as useful in languages that enforce immutability as it is in languages that allow mutation. The fact that you can update in-place is a nice bonus that gives the algorithm great performance and space characteristics in languages with mutable datastructures, but that implementation detail is not an inherent part of the beauty of the algorithm. It's relevant because weavejester suggested quicksort is easier to implement in an imperative language.
    - xyzzyz 15y ago
      No, the demonstration of divide-and-conquer strategy is the merge sort. The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time -- that's why it is called quicksort, actually. This naive implementation is neither fast, nor in place, nor quicksort.
      - kenjackson 15y ago
        No, the demonstration of divide-and-conquer strategy is the merge sort. So is Quicksort. There needn't be just one algorithm that demonstrates divide and conquer. The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time That's not the whole point of quicksort. It is done in-place, but that's just a great side effect of the algorithm. But assuming a cacheless memory model (for example the RAM model) the complexity of the out-of-place version is unchanged. The great thing about QS, IMO, is that it's easy to implement and typically O(n log n). When it is quadratic it is slow -- being in-place only barely makes the quadratic version more tolerable. With that said, I know what you're saying :-) If you read "Purely Functional Data Structures" there are a lot of tree/graph manipulations that are cake to do in C, but are a bear in ML/Haskell. A great programmer has all tools at her disposal, not just one (even if it is finely tuned).
  - yoklov 15y ago
    You know, I actually thought about mentioning that it wasn't quite exactly the same, but decided against because I really do think that it's still quicksort. Is it identical? No, you're right, it's not. But it still is an expression of the same algorithm. Modifying the array in place is a inherently imperative technique, and while you /could/ do something like that in Haskell using, say, Data.Array.ST, you would loose the expressiveness of programming functionally and be programming imperatively just for the heck of it. Trying to solve a problem in a functional language exactly the same as in an imperative one is foolish. They're different paradigms with different strengths and weaknesses, and if you try to map concepts 100% from one to another, it will often end in tears.
    - xyzzyz 15y ago
      That's what I actually meant -- quicksort shows where the imperative approach shines, and using it as an example of functional programming is a particularly bad idea, because naive implementation is not relevant and serious one (in place sorting of random-access sequences) is quite complicated and not elegant at all. It's just the example of the fact that not all algorithms can be efficiently implemented in purely functional manner, just like not all algorithms can be elegantly implemented using only imperative techniques. There's no silver bullet.
dwc 15y ago
Minor[1] nit: quicksort is not a problem, it's a solution to a problem. The problem in question in efficient general-purpose sorting. 1. It may not be such a minor nit. Too often comparisons are made based on implement algorithm X where the algo is something that is specific to, say, imperative programming. This leads to endless and mostly meaningless arguments.
comex 15y ago
If you are designing a program, even in an impure language, it's a good idea to design it so that it never has to do this. It's confusing and bad style. But if you've already designed the program, and you want to make a semantically minor change that requires linking formerly unrelated parts of the program, an impure language lets you do it without modifying half the program to keep up with new signatures. I think the fact that the author is writing games-- where the user literally interacts with a big mutable world, and "when A happens, B should happen" is a natural request-- magnifies the problem, but it could happen anywhere. Actually, I can think of an example: in New Super Mario Bros. Wii, there is a nice toy feature where when the music reaches a certain point, the enemies dance to it: http://www.youtube.com/watch?v=s03Kco-XQCY http://www.youtube.com/watch?v=s03Kco-XQCY . I don't know anything about the actual development of the game, but as this doesn't significantly affect gameplay, I could imagine that this feature was added late in development, making what was formerly a one-way pipe from gameplay to sound into two-way communication. In a well designed program in a pure language, wouldn't this be hard to implement?
- yummyfajitas 15y ago
  But if you've already designed the program, and you want to make a semantically minor change that requires linking formerly unrelated parts of the program, an impure language lets you do it without modifying half the program to keep up with new signatures. I'd rephrase this slightly. If you want to make a semantically minor change that involves linking formerly unrelated parts of a program, an impure language permits you to do so without thinking through the effects this might have on your whole program. In contrast, a pure program forces you to walk through your code and replace "a -> a" with "a -> GameState a" in every single function that might have broken. This includes the functions you might have forgotten about. Now lets look at how this would explicitly work in your example of dancing enemies. In a pure functional language, your game logic is probably something along the lines of GameState a = State GameWorld a, with GameWorld a type describing the state of your world. To add the dancing koopa troopa logic, you'd merely need to modify the GameState object and include (MusicTrack, MusicTime) as a field. There would be very little messing around with type signatures - the function advanceEnemyState: () -> GameState EnemyState is already expected to vary based on the world.

yoklov 15y ago

Agreed, but just because: Quicksort in Haskell: quicksort [] = [] quicksort (x:xs) = quicksort front ++ [x] ++ quicksort behind where front = filter (<= x) xs behind = filter (> x) xs

xyzzyz 15y ago
I hate this example. This is not what quicksort is about. Quicksort is about sorting array in place. The preceding code is not. Also I can't see how it's relevant to the thread.
- Confusion 15y ago
  Quicksort is the demonstration of the divide-and-conquer strategy, which is just as useful in languages that enforce immutability as it is in languages that allow mutation. The fact that you can update in-place is a nice bonus that gives the algorithm great performance and space characteristics in languages with mutable datastructures, but that implementation detail is not an inherent part of the beauty of the algorithm. It's relevant because weavejester suggested quicksort is easier to implement in an imperative language.
  - xyzzyz 15y ago
    No, the demonstration of divide-and-conquer strategy is the merge sort. The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time -- that's why it is called quicksort, actually. This naive implementation is neither fast, nor in place, nor quicksort.
    - kenjackson 15y ago
      No, the demonstration of divide-and-conquer strategy is the merge sort. So is Quicksort. There needn't be just one algorithm that demonstrates divide and conquer. The whole point of quicksort is that it is in place, which makes it fast in spite of the pessimistic quadratic time That's not the whole point of quicksort. It is done in-place, but that's just a great side effect of the algorithm. But assuming a cacheless memory model (for example the RAM model) the complexity of the out-of-place version is unchanged. The great thing about QS, IMO, is that it's easy to implement and typically O(n log n). When it is quadratic it is slow -- being in-place only barely makes the quadratic version more tolerable. With that said, I know what you're saying :-) If you read "Purely Functional Data Structures" there are a lot of tree/graph manipulations that are cake to do in C, but are a bear in ML/Haskell. A great programmer has all tools at her disposal, not just one (even if it is finely tuned).
- yoklov 15y ago
  You know, I actually thought about mentioning that it wasn't quite exactly the same, but decided against because I really do think that it's still quicksort. Is it identical? No, you're right, it's not. But it still is an expression of the same algorithm. Modifying the array in place is a inherently imperative technique, and while you /could/ do something like that in Haskell using, say, Data.Array.ST, you would loose the expressiveness of programming functionally and be programming imperatively just for the heck of it. Trying to solve a problem in a functional language exactly the same as in an imperative one is foolish. They're different paradigms with different strengths and weaknesses, and if you try to map concepts 100% from one to another, it will often end in tears.
  - xyzzyz 15y ago
    That's what I actually meant -- quicksort shows where the imperative approach shines, and using it as an example of functional programming is a particularly bad idea, because naive implementation is not relevant and serious one (in place sorting of random-access sequences) is quite complicated and not elegant at all. It's just the example of the fact that not all algorithms can be efficiently implemented in purely functional manner, just like not all algorithms can be elegantly implemented using only imperative techniques. There's no silver bullet.

dwc 15y ago

Minor[1] nit: quicksort is not a problem, it's a solution to a problem. The problem in question in efficient general-purpose sorting. 1. It may not be such a minor nit. Too often comparisons are made based on implement algorithm X where the algo is something that is specific to, say, imperative programming. This leads to endless and mostly meaningless arguments.

comex 15y ago

If you are designing a program, even in an impure language, it's a good idea to design it so that it never has to do this. It's confusing and bad style. But if you've already designed the program, and you want to make a semantically minor change that requires linking formerly unrelated parts of the program, an impure language lets you do it without modifying half the program to keep up with new signatures. I think the fact that the author is writing games-- where the user literally interacts with a big mutable world, and "when A happens, B should happen" is a natural request-- magnifies the problem, but it could happen anywhere. Actually, I can think of an example: in New Super Mario Bros. Wii, there is a nice toy feature where when the music reaches a certain point, the enemies dance to it: http://www.youtube.com/watch?v=s03Kco-XQCY http://www.youtube.com/watch?v=s03Kco-XQCY . I don't know anything about the actual development of the game, but as this doesn't significantly affect gameplay, I could imagine that this feature was added late in development, making what was formerly a one-way pipe from gameplay to sound into two-way communication. In a well designed program in a pure language, wouldn't this be hard to implement?

yummyfajitas 15y ago
But if you've already designed the program, and you want to make a semantically minor change that requires linking formerly unrelated parts of the program, an impure language lets you do it without modifying half the program to keep up with new signatures. I'd rephrase this slightly. If you want to make a semantically minor change that involves linking formerly unrelated parts of a program, an impure language permits you to do so without thinking through the effects this might have on your whole program. In contrast, a pure program forces you to walk through your code and replace "a -> a" with "a -> GameState a" in every single function that might have broken. This includes the functions you might have forgotten about. Now lets look at how this would explicitly work in your example of dancing enemies. In a pure functional language, your game logic is probably something along the lines of GameState a = State GameWorld a, with GameWorld a type describing the state of your world. To add the dancing koopa troopa logic, you'd merely need to modify the GameState object and include (MusicTrack, MusicTime) as a field. There would be very little messing around with type signatures - the function advanceEnemyState: () -> GameState EnemyState is already expected to vary based on the world.