Primes one-liner in Haskell – oh my!

mux on #haskell pasted what is perhaps the most beautiful code I’ve ever seen in my life:

      <mux> > nubBy(((>1) .) . gcd) [2..]
<lambdabot>  [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,...

(Number two in an ongoing series of jaw-dropping Haskell one-liners which began with the fibonacci series.)

5 Responses to “Primes one-liner in Haskell – oh my!”

  1. May 8th, 2007 | 12:04 pm

    Personally, I find sections of (.) to be rather unreadable. It takes me rather a long time to figure out what they do! By contrast, I doubt you’ll find a more concise specification of stable quicksort than this:

    quicksort :: Ord a => [a] -> [a]
    quicksort [] = []
    quicksort (x:xs) = quicksort ( x) xs

    And something else that will blow your mind: because of lazy evaluation,

    head . quicksort

    (which finds the smallest element in a list) is O(n).

  2. csoroz
    March 20th, 2008 | 2:11 am

    Reduction of (.):

    
    f.g = \x -> f (g x)
    
    ((>1) .) . gcd 
     = \x -> ((>1) .) (gcd x)
     = \x -> (>1) . (gcd x)
     = \x -> \y -> (>1) ((gcd x) y)
     = \x y -> (>1) (gcd x y)
     = \x y -> (gcd x y) > 1
    

  3. csoroz
    March 22nd, 2008 | 4:41 pm

    A more efficient (more beautiful?) solution:

    
    nubBy (((==0) .) . (flip mod)) [2..]
    

  4. A Groeneveld
    April 2nd, 2008 | 11:56 am

    A more efficient (less beuatifull?) solution:

    (2 :). nubBy (((==0) .) . flip mod) $ [3,5..]

  5. csoroz
    September 30th, 2009 | 10:30 pm

    Solutions from comments 3 and 4 didn’t work.

    This is because the comparison function depends on the order of parameters (due to mod) and, apparently, nubBy doesn’t guarantees that always is gonna use it in the same way.

    With Hugs the result is OK:

    
    Hugs> :l Data.List
    Data.List> take 10 $ nubBy (((>1) .) . gcd) [2..]
    [2,3,5,7,11,13,17,19,23,29]
    Data.List> take 10 $ nubBy (((==0) .) . flip mod) [2..]
    [2,3,5,7,11,13,17,19,23,29]
    

    But GHC/GHCi (6.10.3-6.10.4) gives:

    
    Prelude> :m +Data.List
    Prelude Data.List> take 10 $ nubBy (((>1) .) . gcd) [2..]
    [2,3,5,7,11,13,17,19,23,29]
    Prelude Data.List> take 10 $ nubBy (((==0) .) . flip mod) [2..]
    [2,3,4,5,6,7,8,9,10,11]
    

    whereas:

    
    Prelude Data.List> take 10 $ nubBy (((==0) .) . mod) [2..]
    [2,3,5,7,11,13,17,19,23,29]