Calculate your Eddington number

eddington.hs

-- Given this in Lisp:
-- (defn eddington [a] (count (filter true? (keep-indexed < (reverse (sort a))))))
-- do it in Haskell (thanks to @zimpenfish for the original)

import Data.List

-- keep-indexed f l applies f over l and keeps the result of anything that is
-- not nil. f takes two arguments, index of list item and list item

-- We can do this in Haskell by zipping the original list with the indices
-- then mapping over it (being a Real Language, we don't have nil, so the
-- operation is actually a map - we can't throw away things that don't exist :)

with_index l = zip [0..length l] l

pair_apply f p = f (fst p) (snd p)

map_indexed f l = map (pair_apply f) $ with_index l

-- and so we can re-implement the algorithm thus:

eddington l =
  let
    mapped = map_indexed (<) $ reverse (sort l)
  in
    length $ filter id mapped

-- But hold on, that map to true/false followed by a filter can be
-- turned into a simple filter

filter_indexed f l = map snd $ filter (pair_apply f) $ with_index l

-- Giving...

eddington2 l =
  length $ filter_indexed (<) $ reverse (sort l)

-- (or, and I think this is equivalent, you can use takeWhile, because
-- the once the index exceeds the entry in the reverse-sorted list,
-- it can never be lower than it again, so we can benefit from early
-- termination and use takeWhile instead)

take_indexed f l = map snd $ takeWhile (pair_apply f) $ with_index l

eddington2b l =
  length $ take_indexed (<) $ reverse (sort l)

-- Sooo....

transform_indexed f g l = map snd $ f (pair_apply g) $ with_index l

-- (which means we can define...)

take_indexed2 f l = transform_indexed takeWhile f l
filter_indexed2 f l = transform_indexed filter f l

-- And thus we get...

eddington3 l =
  length $ transform_indexed filter (<) $ reverse (sort l)

eddington3b l =
  length $ transform_indexed takeWhile (<) $ reverse (sort l)

-- But we don't actually care about the result of the filter/map,
-- just the length of the list

eddington4 l =
  length $ filter (pair_apply (<)) $ with_index $ reverse (sort l)

eddington4b l =
  length $ takeWhile (pair_apply (<)) $ with_index $ reverse (sort l)

-- And so if we substitute in for our other functions

eddington_oneline l =
  length $ filter (\p -> fst p < snd p) $ zip [0..length l] $ reverse (sort l)

eddington_oneline_b l =
  length $ takeWhile (\p -> fst p < snd p) $ zip [0..length l] $ reverse (sort l)

-- Or if you prefer brackets

eddington_lispy l =
  length (filter (\p -> fst p < snd p) (zip [0..length l] (reverse (sort l))))

eddington_lispy_b l =
  length (takeWhile (\p -> fst p < snd p) (zip [0..length l] (reverse (sort l))))

-- Of course, composing it out of more general utility functions is nicer
-- and expresses intent more cleanly; the original was a one-liner and it's
-- nice to see we can do it in Haskell too.

-- For bonus fun, compare
-- > eddington [1,2,3]
-- with
-- > let l = [1,2,3]
-- > eddington l