Why isn't Haskell popular in industry?

However I think that you didn't pick the best example.

I tried out:

>head $ sort [1 .. 10000000]

6 secs, using ~2g of heap! (actually is should be a reverse sort)

and the "hand coded loop":

>let mx (x:xs) m = if x > m then mx xs x else mx xs m; mx [] m = m >mx [1 .. 10000000] 0

3 secs, heap usage stays negligible low and constant.

Something is clearly not behaving as you depicted.

(of course my 'loop' code is not the exact equivalent of the last.sort composition, since it requires a 'minimum' parameter to be passed in advance, which not all types have. On the other hand it works also for the empty list)

I also have the feeling that, unless special compiler optimization (a very 'specific' one, I fear), the simple application of the 'head' function to a sorted list would stop when the first result element is produced, which is not after O(n). Granted, you don't have to wait for a full sort, since the sorting algorithm could guarantee that the rest of the list contain 'lesser/bigger' elements only and thus stop. But keeping track of all this should be space consuming, in respect to a simple linear scan.

Anyway the space problem of the "lazy" solution is a bigger issue than the number of comparisons.

I'm not a haskell master, but if I got it right, one of the mayor problems of lazy programming is that in some situations it can degenerate to a huge amounts of "unevaluated thunks", which are frozen computations yet to be performed, but which require some state to be held in memory (like function arguments, I guess).

(http://www.haskell.org/haskellwiki/Thunk)

or in this case, the space usage is caused simply because the list has to be materialized in memory instead of be simply traversed and generated on the fly. (but 2g seems slightly too much).

Anyway, the point here is that the two methods are not equivalent.

I think that understanding the impact of laziness on space is an issue that certainly increases the learning curve, as it requires time to master this and other optimization techniques if you want to get predictable performances from haskell.

(BTW, I actually use haskell for work, perhaps in a slightly conterintuitive way. I use haskell for quick prototyping ideas and solutions. Sometimes I get inspired by the solution I end up with haskell and translate it in clojure or java (work requirement), or at other times I have to rewrite it completely, but the possibility to quickly prototype in haskell really helps me a lot. I would love a stable ghc JVM backend.... it would change my life)

Let's use the List monad to determine someone's roommates.

    > import Control.Applicative
    > import Data.List

    > type Person = String
    > type Address = String

    > addresses :: [(Person, Address)]
    > addresses = [("jrockway", "123 Fake St."), ("jrockway's cat", "123 Fake St.")]

    > people :: [(Address, Person)]
    > people = uncurry (flip (,))  addresses

    > assocFilter :: Eq a => a -> [(a,b)] -> [b]
    > assocFilter p xs = snd  filter ((==p) . fst) xs

    > addressesForPerson person = assocFilter person addresses
    > peopleAtAddress address = assocFilter address people

    > roommatesFor :: Person -> [Person]
    > roommatesFor person = do
    >     address      peopleAtAddress address

BTW, you can just cut-n-paste this into a .lhs file and run it, if you want to try it out.

http://apfelmus.nfshost.com/articles/quicksearch.html

As far as I can understand from the blog and and the cited mailing lists, it works but it requires a carefully coded sorting method, otherwise O(n log n) as expected.

  elemIndex :: a -> [a] -> Maybe Int
  lookup :: k -> Map k a -> Maybe a

  lookup key map >>= elemIndex "foobar"

Not very impressive, but monads aren't anything groundbreaking after all, they're just utilities that make our lives easier. There are more complicated operations that come in handy later, but they are quite straightforward once you get a grasp of the container metaphor.

Yes, it's triggers my Rainman instincts to point out that 1. It should be max = last . sort 2. Or min = head . sort 3. You are making assumptions on the sorting algorithm to make it possible to short-cut the evaluation.

K-MART! K-MART! :)

Edit: How nice of you to downvote...