5 ms·

Is it actually possible to implement quicksort in a pure functional language like Haskell (with immutable data structures)? Sorting in place would seem to invol

by chris_j 16y ago

Is it actually possible to implement quicksort in a pure functional language like Haskell (with immutable data structures)? Sorting in place would seem to involve mutating the list every time two values are swapped.

jmillikin 16y ago
Haskell has mutable data structures; you could easily implement in-place quicksort with vectors, arrays, or pointers.
Hemospectrum 16y ago
Haskell is designed to quarantine side effects, not remove them altogether. There's a special monad for building data structures that are mutable at creation time but appear immutable outside that block of code. In normal circumstances, you'd probably still have to copy the contents of the input into a new array before sorting it, though. So, it would still be less memory efficient on large inputs.
danieldk 16y ago
Yes. For example, the vector package provides mutable arrays: http://hackage.haskell.org/package/vector-0.7.0.1 http://hackage.haskell.org/package/vector-0.7.0.1 Mutability is attained by using the ST monad. The ST monad uses mutable memory, but since it does not allow other interactions with the outside world, its value can be extracted (unlike the IO monad). When you are done with the modification of the vector, it can be frozen to obtain a pure vector. The IO monad can also be used, but not if you want to return a pure value. A good tutorial can be found at: http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector_Tutorial http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector... I used mutable vectors in the ST monad in maximum entropy training software, and they are really performant.
- KirinDave 16y ago
  What blew my mind about the ST monad is that despite its promise of single-threading, it still allows for recursive division of labor. I was like, "Wait. Wait. Waaaiiiitt. How does it do that?"

5 ms·

Is it actually possible to implement quicksort in a pure functional language like Haskell (with immutable data structures)? Sorting in place would seem to invol

by chris_j 16y ago

jmillikin 16y ago
Haskell has mutable data structures; you could easily implement in-place quicksort with vectors, arrays, or pointers.
Hemospectrum 16y ago
Haskell is designed to quarantine side effects, not remove them altogether. There's a special monad for building data structures that are mutable at creation time but appear immutable outside that block of code. In normal circumstances, you'd probably still have to copy the contents of the input into a new array before sorting it, though. So, it would still be less memory efficient on large inputs.
danieldk 16y ago
Yes. For example, the vector package provides mutable arrays: http://hackage.haskell.org/package/vector-0.7.0.1 http://hackage.haskell.org/package/vector-0.7.0.1 Mutability is attained by using the ST monad. The ST monad uses mutable memory, but since it does not allow other interactions with the outside world, its value can be extracted (unlike the IO monad). When you are done with the modification of the vector, it can be frozen to obtain a pure vector. The IO monad can also be used, but not if you want to return a pure value. A good tutorial can be found at: http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector_Tutorial http://www.haskell.org/haskellwiki/Numeric_Haskell:_A_Vector... I used mutable vectors in the ST monad in maximum entropy training software, and they are really performant.
- KirinDave 16y ago
  What blew my mind about the ST monad is that despite its promise of single-threading, it still allows for recursive division of labor. I was like, "Wait. Wait. Waaaiiiitt. How does it do that?"