Walter Bright:

> Except that isn't really quicksort. Monads are the workaround functional languages use to deal with things that need mutation.

Take also a look at "Clean" language. It doesn't use monads and it's a very efficient functional language.

Bye,
bearophile

On Friday, 21 November 2014 at 02:56:09 UTC, Andrei Alexandrescu wrote:
> On 11/20/14 5:09 PM, Walter Bright wrote:
>> On 11/20/2014 3:10 PM, "Ola Fosheim Grøstad"
>> <ola.fosheim.grostad+dlang@gmail.com>" wrote:
>>> On Thursday, 20 November 2014 at 22:47:27 UTC, Walter Bright wrote:
>>>> On 11/20/2014 1:55 PM, deadalnix wrote:
>>>>> All of this is beautiful until you try to implement a quicksort
>>>>> in, haskell.
>>>
>>> […]
>>>
>>>> Monads!
>>>
>>> I think Deadalnix meant that you cannot do in-place quicksort easily
>>> in Haskell.
>>
>> That's correct.
>>
>>> Non-mutating quicksort is easy, no need for monads:
>>>
>>> quicksort []     = []
>>> quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
>>>     where
>>>         lesser  = filter (< p) xs
>>>         greater = filter (>= p) xs
>>>
>>> https://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
>>
>> Except that isn't really quicksort. Monads are the workaround functional
>> languages use to deal with things that need mutation.
>
> As I like to say, this troika has inflicted a lot of damage on both FP and those beginning to learn it:
>
> * Linear-space factorial
> * Doubly exponential Fibonacci
> * (Non)Quicksort
>
> These losers appear with depressing frequency in FP introductory texts.
>
>
> Andrei

Just like the OOP introductory books that still insist in talking about Cars and Vehicles, Managers and Employees, Animals and Bees, always using inheritance as code reuse.

Barely talking about is-a and has-a, and all the issues about fragile base classes.

--
Paulo

On Friday, 21 November 2014 at 02:56:09 UTC, Andrei Alexandrescu wrote:
> As I like to say, this troika has inflicted a lot of damage on both FP and those beginning to learn it:
>
> * Linear-space factorial
> * Doubly exponential Fibonacci
> * (Non)Quicksort
>
> These losers appear with depressing frequency in FP introductory texts.

Be careful with that attitude. It is an excellent strategy to start with the simple implementation and then move on to other techniques in later chapters or more advanced texts.

https://www.haskell.org/haskellwiki/The_Fibonacci_sequence
https://www.haskell.org/haskellwiki/Memoization

Some compilers are even capable of adding memoization/caching behind the scenes which brings naive fibonacci down to O(n) with no change in the source.

Also, keep in mind that non-mutating quick sort has the same space/time complexity as the mutating variant. The non-mutating variant is no doubt faster on massively parallel hardware. You can do quicksort on GPUs.

The landscape of performance and complexity is not so simple these days.

On 11/21/14 12:17 AM, Paulo Pinto wrote:
> On Friday, 21 November 2014 at 02:56:09 UTC, Andrei Alexandrescu wrote:
>> On 11/20/14 5:09 PM, Walter Bright wrote:
>>> On 11/20/2014 3:10 PM, "Ola Fosheim Grøstad"
>>> <ola.fosheim.grostad+dlang@gmail.com>" wrote:
>>>> On Thursday, 20 November 2014 at 22:47:27 UTC, Walter Bright wrote:
>>>>> On 11/20/2014 1:55 PM, deadalnix wrote:
>>>>>> All of this is beautiful until you try to implement a quicksort
>>>>>> in, haskell.
>>>>
>>>> […]
>>>>
>>>>> Monads!
>>>>
>>>> I think Deadalnix meant that you cannot do in-place quicksort easily
>>>> in Haskell.
>>>
>>> That's correct.
>>>
>>>> Non-mutating quicksort is easy, no need for monads:
>>>>
>>>> quicksort []     = []
>>>> quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
>>>>     where
>>>>         lesser  = filter (< p) xs
>>>>         greater = filter (>= p) xs
>>>>
>>>> https://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell
>>>
>>> Except that isn't really quicksort. Monads are the workaround functional
>>> languages use to deal with things that need mutation.
>>
>> As I like to say, this troika has inflicted a lot of damage on both FP
>> and those beginning to learn it:
>>
>> * Linear-space factorial
>> * Doubly exponential Fibonacci
>> * (Non)Quicksort
>>
>> These losers appear with depressing frequency in FP introductory texts.
>>
>>
>> Andrei
>
> Just like the OOP introductory books that still insist in talking about
> Cars and Vehicles, Managers and Employees, Animals and Bees, always
> using inheritance as code reuse.

The first public example found by google (oop introduction) lists a class Student as the first example of a class:

http://www.codeproject.com/Articles/22769/Introduction-to-Object-Oriented-Programming-Concep#Object

and IOException inheriting Exception as the first example of inheritance:

http://www.codeproject.com/Articles/22769/Introduction-to-Object-Oriented-Programming-Concep#Inheritance

First example for overriding is Complex.ToString:

http://www.codeproject.com/Articles/22769/Introduction-to-Object-Oriented-Programming-Concep#Overloading

> Barely talking about is-a and has-a, and all the issues about fragile
> base classes.

Even to the extent those old texts have persisted, they are "only" poor style. In contrast, the three FP example I mentioned are computationally bankrupt. There is really no excuse for teaching them.


Andrei

>
> Just like the OOP introductory books that still insist in talking about Cars and Vehicles, Managers and Employees, Animals and Bees, always using inheritance as code reuse.
>
> Barely talking about is-a and has-a, and all the issues about fragile base classes.
>
> --
> Paulo

Hear, hear. One of the problems with many introductions to OOP-paradigmed languages such as C++ is that by having to spend a lot of time explaining how to implement inheritance, the novice reader thinks that OOP is the 'right' approach to solving many problems when in fact other techniques ('prefer composition over inheritance' springs to mind) are far more appropriate. This is one of the primary problems I find in code of even more experienced programmers.

On Friday, 21 November 2014 at 16:07:20 UTC, Abdulhaq wrote:
> Hear, hear. One of the problems with many introductions to OOP-paradigmed languages such as C++ is that by having to spend a lot of time explaining how to implement inheritance, the novice reader thinks that OOP is the 'right' approach to solving many problems when in fact other techniques ('prefer composition over inheritance' springs to mind) are far more appropriate. This is one of the primary problems I find in code of even more experienced programmers.

Yes, the problem is that you should not teach OOP, but object oriented analysis and object oriented modelling in a language agnostic fashion… but you need to touch both structured and object oriented programming first to create motivation in the student for learning analysis and modelling…

The same goes for performance and complexity. You should only cover structured programming/abstraction in the first programming course with no hindsight to performance, then touch performance and algorithmic complexity in the second course, then do complexity proofs in an advanced course.

If a single course cover too much ground students get confused, the learning goals become hazy and you loose half your audience.