← Back to context

Comment by antonvs

14 days ago

> easy problems tough.

That needs a qualifier: it can make easy problems tough if you're not familiar with how to solve them in a functional context.

A big part of that is because smart people have already solved the tough problems and made them available as language features or libraries.

11 comments

antonvs

Reply
cubefox  14 days ago

> That needs a qualifier: it can make easy problems tough if you're not familiar with how to solve them in a functional context.

All problems are easy if you are familiar with how to solve them. Unfortunately it's part of the problem to find out how to solve them, and that can be unusually hard in case of functional programming. Like solving something with recursion instead of loops + states. There is a reason cookbooks use loops not recursion.

simiones  14 days ago

Not really, certain problems are just inherently harder to express in a purely functional way than they are in an imperative way (and the reverse is just as true). For example, computing a histogram is much simpler in imperative terms (keep an array of histogram values, go through the original list, add 1 to the array element corresponding to the current element in this list) than in a purely functional style, especially if you need a somewhat efficient implementation.

My favorite example of this is implementing quicksort. It's significantly easier in C than it is in Haskell.

  • chuckadams  14 days ago

    > My favorite example of this is implementing quicksort. It's significantly easier in C than it is in Haskell.

    Oh please, what's so hard about

        qsort :: Ord a => [a] -> [a]
    qsort []     = []
    qsort (p:xs) = qsort lesser ++ [p] ++ qsort greater
        where
            lesser  = filter (< p) xs
            greater = filter (>= p) xs

    :)

    folks, take that with a big ol /s, you would never want to actually use that algorithm. But the real deal isn't all that awful: https://mmhaskell.com/blog/2019/5/13/quicksort-with-haskell

    • trealira  14 days ago

      I know you're being sarcastic, but even in this linked-list quicksort, it could be made more efficient. By defining lesser and greater separately, you're traversing the list twice. You could compute them at the same time by changing those last two lines to this:

        where
    (lesser, greater) = partition (< p) xs

      I just learned about the existence of this function today, and wonder why I had never seen it used before.

      https://hackage.haskell.org/package/base-4.20.0.1/docs/Data-...

      1 reply →

    • hnfong  14 days ago

      Arguably the issue with "quicksort in Haskell" is not that it's "hard" to implement, but rather it defeats the whole purpose of using a "purely functional" language.

      The pragmatic way to look at Haskell is not that it's purely functional, but rather, you could write <del>imperative code</del> Monads if you wanted, and that gives a "functional by default" environment, whereas most imperative languages default to mutable objects etc that are not friendly to functional-style programming.

      But then the more modern languages are catching on with immutable by default variables etc. so in the end the differences between newer languages may not be that great after all...

    • simiones  14 days ago

      Well, I'd say using an entirely different collection type than the rest of language (STArray instead of [a]) is already a big complication. It also ends up being more than double the size of the Java code. And, as the author admits, it's actually even slower than the original not-quicksort implementation above, because it actually has to make a copy of the original list, and then return a copy of the mutated array.

      So, one of the best sorting algorithms ever devised is not actually usable to sort a [a] in Haskell... I maintain this is a good example of making an easy problem tough.

      2 replies →