6 ms·

Neat! A nitpick: I haven't used Haskell, so I'm trying to read the prime sieve example in the corner, but there's very little contrast between the background an

by matchu 12y ago

Neat! A nitpick: I haven't used Haskell, so I'm trying to read the prime sieve example in the corner, but there's very little contrast between the background and the nonalphanumeric characters. Some brighter syntax highlighting would be a better choice against that dark background.

MBCook 12y ago
Agreed. That punctuation almost disappears depending on the angle of my laptop screen.
Touche 12y ago
Also maybe pick a simpler example and not play into the stereotype that Haskell is for people who think they are smarter than everyone else.
- vamega 12y ago
  Could you suggest a simpler example? Finding primes is something that is taught in the first programming class in Indian high schools. I guess I've never thought of it as something hard. I looked at nodejs.org, and their first example is a web server! Python has the Fibonacci as it's second example (the first one show's numeric operations). Ruby does simple string operations on it's home page. While I think that is indeed simpler, it's a little nuanced in Haskell. Depending on how you're doing it you'll need to Map toUpper from Data.Char or use toUpper from Data.Text, and I don't think it's a good first impression have something that uses Data.Text, and the OverloadedStrings extension. PS - Although, I do agree with some other commentors here that this code isn't actually the Sieve of Eratosthenes, and is far more inefficient, and that is a valid reason to replace that example.
  - tel 12y ago
    Well, for one, it's a bad sieve algorithm. I think a neat algorithm to demonstrate laziness and Haskell clarity would be enumerating the Calkin-Wilf rationals. [0] It's quite a bit longer but demonstrates a number of neat ideas. I'll start first with a derivation which demonstrates all of the structure of the algorithm and then go through a series of mechanical transforms so that by the end I have a one-liner and a comparable Python implementation. The first algorithm comes directly from the paper and uses an intermediary infinite tree to represent the rationals. data BTree a = Node a (BTree a) (BTree a) fold :: (a -> x -> x -> x) -> BTree a -> x fold f (Node a l r) = f a (fold f l) (fold f r) unfold :: (x -> (a, x, x)) -> x -> BTree a unfold f x = let (a, l, r) = f x in Node a (unfold f l) (unfold f r) breadthFirst :: BTree a -> [a] breadthFirst = concat . fold glue where glue a ls rs = [a] : zipWith (++) ls rs allRationals :: Fractional a => [a] allRationals = breadthFirst (unfold step (1, 1)) where step (m, n) = ( m/n, (m, m+n) , (n+m, n) ) In 16 lines I've got an infinite binary tree, its natural fold and unfold, a breadth first search, and a lazy algorithm for generating all of the rationals with no repeats. The whole thing is simple, natural, beautiful, and efficient! It demonstrates infinite recursive types, laziness, higher-order functions, and bounded polymorphism. And also a neat algorithm! The downside is that 16 lines is pretty long. By inlining the fold and unfold I can get it down to 9 lines: data BTree a = Node a (BTree a) (BTree a) breadthFirst :: BTree a -> [a] breadthFirst = concat . glue where glue (Node a ls rs) = [a] : zipWith (++) (glue ls) (glue rs) rats :: Fractional a => [a] rats = breadthFirst (generate (1, 1)) where generate (m, n) = Node (m/n) (generate (m, m+n)) (generate (n+m, n)) If I'm allowed imports we can use Data.Tree and make this a one-liner! import Data.Tree allRationals :: Fractional a => [a] allRationals = flatten (unfoldTree step (1, 1)) where step (m, n) = ( m/n, [ (m, m+n), (n+m, n) ] ) Finally, if I go another route and fuse the fold and unfold together into a hylomorphism data Trip a x = Trip a x x deriving Functor hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b hylo phi psi = phi . fmap (hylo phi psi) . psi allRationals :: Fractional a => [a] allRationals = concat (hylo glue step (1, 1)) where glue (Trip a ls rs) = [a] : zipWith (++) ls rs step (m, n) = Trip (m/n) (m, m+n) (n+m, n) we can hide the tree entirely and demonstrate `deriving`... at considerable cost to clarity! With a little more golfing (read: inlining) we arrive at this beauty: allRationals :: Fractional a => [a] allRationals = concat (go (1, 1)) where go = glue . next . step next (a, b, c) = (a, f b, f c) glue (a, ls, rs) = [a] : zipWith (++) ls rs step (m, n) = ( m/n, (m, m+n), (n+m, n) ) which at least has the bonus of demonstrating some nice co-recursion between go and next. Or even, ultimately: allRationals :: Fractional a => [a] allRationals = concat (go 1 1) where go m n = [m/n] : zipWith (++) (go m (m+n)) (go (n+m) n) which is actually kind of nice again if almost all of the structure has vanished. Note that if `interleave` were part of the Prelude then we could write allRationals :: Fractional a => [a] allRationals = go 1 1 where go m n = (m/n) : interleave (go m (m+n)) (go (n+m) n) given interleave :: [a] -> [a] -> [a] interleave [] ys = ys interleave xs [] = xs interleave (x:xs) (y:ys) = x : y : interleave xs ys which is a little prettier and directly comparable to something Pythonic like from fractions import Fraction from itertools import islice def interleave(x, y): while True: yield x.next() yield y.next() def all_rationals(): def go(m, n): yield (m/n) for v in interleave(go(m, m+n), go(m+n, n)): yield v return go(Fraction(1,1), Fraction(1,1)) def rationals(n): return list(islice(all_rationals(), n)) [0] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals...
    - gipp 12y ago
      It's also utterly incomprehensible for someone who hasn't seen Haskell before. Whereas with the existing example, one can at least piece together an idea of what's going on. The point is to demonstrate the directness of expression and conciseness of Haskell, not to show how to create an efficient implementation of an involved algorithm.
      - tel 12y ago
        I agree that the first formulation is a bit incomprehensible, though two-liner breadth-first search is understandable if a bit amazing. Some of the latter versions (and perhaps ultimately the very last version) are easier to walk through for a beginner, though, and are calculated from properties expressed in the first.
    - deleted 12y ago
      [deleted]
    - dcre 12y ago
      Wonderful comment, but I have a math degree and Haskell experience. This stuff would be insane to drop on a beginner.
      - tel 12y ago
        I'm hoping to simplify it!
    - mweibel 12y ago
      To be honest: This would turn me off even more than the current example which is also hard to read/understand as a non Haskell programmer. The fibonacci example in another comment in this thread however is very easy to understand and would fit much better.
      - tel 12y ago
        Even the one-liner form at the end? This comment was really bad at exposition, but I think it got somewhere nice.
  - rtfeldman 12y ago
    Fibonacci sounds perfect! fibonacci :: Integer -> Integer fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n = fibonacci (n - 1) + fibonacci (n - 2) Arguments for this: * "Find the Nth Fibonacci Number" is among the most universally known programming tasks, so visitors are far more likely to immediately pick up the example than they are with sieve. * It shows off a bit of Haskell syntax that (A) can be learned just by looking at an example like this, (B) has a clear benefit to readability that any programmer can appreciate, and (C) is a syntax not found in most mainstream languages. * The visitor needs no functional programming experience to follow it; it doesn't even use any higher-order functions! This is important, as many visitors will be completely new to FP, and an example that they can't follow is not going to be effective at encouraging them to continue reading.
    - danieldk 12y ago
      I think the factorial function is even nicer: everyone with basic high school math has seen it. It's even shorter. Also, I think the example should not be a partial function ;).
    - cousin_it 12y ago
      That's a horrible algorithm though, it takes exponential time. Any good implementation of Fibonacci numbers would be logarithmic in the number of arithmetic operations and polynomial in overall running time (because the numbers get bigger). Here's a good implementation in Haskell: http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/fastFibonacci.hs http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/f... , and the same in Python: http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/fastFibonacci.py http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/f... . BTW, I think even functional programmers would find the Python code slightly easier to follow :-)
      - codygman 12y ago
        Maybe it's because I've been using Haskell exclusively for a few months, but I find the Haskell example more clear. This surprises me because I have much more experience with Python.
      - 12y ago
  - Touche 12y ago
    > Could you suggest a simpler example? Anything that can be Googled and understood what it is trying to accomplish is less than 2 minutes. I tried Googling "sieve" and got nothing of use, then "prime sieve" that has a good wikipedia article that is (probably?) about the correct thing but doesn't fit into the "easily understood in a couple of minutes) rule. So... literally anything. Hello world. First impression shouldn't be that you need to be a math expert to use the language.
- jlebar 12y ago
  FWIW I think the sieve is a great example. Fibonacci is trite and a toy, whereas this is nontrivial and shows off a lot of what's powerful about Haskell (infinite lists, list comprehensions, pattern matching with cons...). It's complex enough that it encourages people to stare at it for a few minutes and engage with it, which is also good. I vote to keep it!
- minikomi 12y ago
  I think it's fine, but could use an "explain" link like on the http://racket-lang.org/ http://racket-lang.org/ homepage.

by matchu 12y ago

MBCook 12y ago

Agreed. That punctuation almost disappears depending on the angle of my laptop screen.

Touche 12y ago

Also maybe pick a simpler example and not play into the stereotype that Haskell is for people who think they are smarter than everyone else.

vamega 12y ago
Could you suggest a simpler example? Finding primes is something that is taught in the first programming class in Indian high schools. I guess I've never thought of it as something hard. I looked at nodejs.org, and their first example is a web server! Python has the Fibonacci as it's second example (the first one show's numeric operations). Ruby does simple string operations on it's home page. While I think that is indeed simpler, it's a little nuanced in Haskell. Depending on how you're doing it you'll need to Map toUpper from Data.Char or use toUpper from Data.Text, and I don't think it's a good first impression have something that uses Data.Text, and the OverloadedStrings extension. PS - Although, I do agree with some other commentors here that this code isn't actually the Sieve of Eratosthenes, and is far more inefficient, and that is a valid reason to replace that example.
- tel 12y ago
  Well, for one, it's a bad sieve algorithm. I think a neat algorithm to demonstrate laziness and Haskell clarity would be enumerating the Calkin-Wilf rationals. [0] It's quite a bit longer but demonstrates a number of neat ideas. I'll start first with a derivation which demonstrates all of the structure of the algorithm and then go through a series of mechanical transforms so that by the end I have a one-liner and a comparable Python implementation. The first algorithm comes directly from the paper and uses an intermediary infinite tree to represent the rationals. data BTree a = Node a (BTree a) (BTree a) fold :: (a -> x -> x -> x) -> BTree a -> x fold f (Node a l r) = f a (fold f l) (fold f r) unfold :: (x -> (a, x, x)) -> x -> BTree a unfold f x = let (a, l, r) = f x in Node a (unfold f l) (unfold f r) breadthFirst :: BTree a -> [a] breadthFirst = concat . fold glue where glue a ls rs = [a] : zipWith (++) ls rs allRationals :: Fractional a => [a] allRationals = breadthFirst (unfold step (1, 1)) where step (m, n) = ( m/n, (m, m+n) , (n+m, n) ) In 16 lines I've got an infinite binary tree, its natural fold and unfold, a breadth first search, and a lazy algorithm for generating all of the rationals with no repeats. The whole thing is simple, natural, beautiful, and efficient! It demonstrates infinite recursive types, laziness, higher-order functions, and bounded polymorphism. And also a neat algorithm! The downside is that 16 lines is pretty long. By inlining the fold and unfold I can get it down to 9 lines: data BTree a = Node a (BTree a) (BTree a) breadthFirst :: BTree a -> [a] breadthFirst = concat . glue where glue (Node a ls rs) = [a] : zipWith (++) (glue ls) (glue rs) rats :: Fractional a => [a] rats = breadthFirst (generate (1, 1)) where generate (m, n) = Node (m/n) (generate (m, m+n)) (generate (n+m, n)) If I'm allowed imports we can use Data.Tree and make this a one-liner! import Data.Tree allRationals :: Fractional a => [a] allRationals = flatten (unfoldTree step (1, 1)) where step (m, n) = ( m/n, [ (m, m+n), (n+m, n) ] ) Finally, if I go another route and fuse the fold and unfold together into a hylomorphism data Trip a x = Trip a x x deriving Functor hylo :: Functor f => (f b -> b) -> (a -> f a) -> a -> b hylo phi psi = phi . fmap (hylo phi psi) . psi allRationals :: Fractional a => [a] allRationals = concat (hylo glue step (1, 1)) where glue (Trip a ls rs) = [a] : zipWith (++) ls rs step (m, n) = Trip (m/n) (m, m+n) (n+m, n) we can hide the tree entirely and demonstrate `deriving`... at considerable cost to clarity! With a little more golfing (read: inlining) we arrive at this beauty: allRationals :: Fractional a => [a] allRationals = concat (go (1, 1)) where go = glue . next . step next (a, b, c) = (a, f b, f c) glue (a, ls, rs) = [a] : zipWith (++) ls rs step (m, n) = ( m/n, (m, m+n), (n+m, n) ) which at least has the bonus of demonstrating some nice co-recursion between go and next. Or even, ultimately: allRationals :: Fractional a => [a] allRationals = concat (go 1 1) where go m n = [m/n] : zipWith (++) (go m (m+n)) (go (n+m) n) which is actually kind of nice again if almost all of the structure has vanished. Note that if `interleave` were part of the Prelude then we could write allRationals :: Fractional a => [a] allRationals = go 1 1 where go m n = (m/n) : interleave (go m (m+n)) (go (n+m) n) given interleave :: [a] -> [a] -> [a] interleave [] ys = ys interleave xs [] = xs interleave (x:xs) (y:ys) = x : y : interleave xs ys which is a little prettier and directly comparable to something Pythonic like from fractions import Fraction from itertools import islice def interleave(x, y): while True: yield x.next() yield y.next() def all_rationals(): def go(m, n): yield (m/n) for v in interleave(go(m, m+n), go(m+n, n)): yield v return go(Fraction(1,1), Fraction(1,1)) def rationals(n): return list(islice(all_rationals(), n)) [0] http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals.pdf http://www.cs.ox.ac.uk/jeremy.gibbons/publications/rationals...
  - gipp 12y ago
    It's also utterly incomprehensible for someone who hasn't seen Haskell before. Whereas with the existing example, one can at least piece together an idea of what's going on. The point is to demonstrate the directness of expression and conciseness of Haskell, not to show how to create an efficient implementation of an involved algorithm.
    - tel 12y ago
      I agree that the first formulation is a bit incomprehensible, though two-liner breadth-first search is understandable if a bit amazing. Some of the latter versions (and perhaps ultimately the very last version) are easier to walk through for a beginner, though, and are calculated from properties expressed in the first.
  - deleted 12y ago
    [deleted]
  - dcre 12y ago
    Wonderful comment, but I have a math degree and Haskell experience. This stuff would be insane to drop on a beginner.
    - tel 12y ago
      I'm hoping to simplify it!
  - mweibel 12y ago
    To be honest: This would turn me off even more than the current example which is also hard to read/understand as a non Haskell programmer. The fibonacci example in another comment in this thread however is very easy to understand and would fit much better.
    - tel 12y ago
      Even the one-liner form at the end? This comment was really bad at exposition, but I think it got somewhere nice.
- rtfeldman 12y ago
  Fibonacci sounds perfect! fibonacci :: Integer -> Integer fibonacci 0 = 0 fibonacci 1 = 1 fibonacci n = fibonacci (n - 1) + fibonacci (n - 2) Arguments for this: * "Find the Nth Fibonacci Number" is among the most universally known programming tasks, so visitors are far more likely to immediately pick up the example than they are with sieve. * It shows off a bit of Haskell syntax that (A) can be learned just by looking at an example like this, (B) has a clear benefit to readability that any programmer can appreciate, and (C) is a syntax not found in most mainstream languages. * The visitor needs no functional programming experience to follow it; it doesn't even use any higher-order functions! This is important, as many visitors will be completely new to FP, and an example that they can't follow is not going to be effective at encouraging them to continue reading.
  - danieldk 12y ago
    I think the factorial function is even nicer: everyone with basic high school math has seen it. It's even shorter. Also, I think the example should not be a partial function ;).
  - cousin_it 12y ago
    That's a horrible algorithm though, it takes exponential time. Any good implementation of Fibonacci numbers would be logarithmic in the number of arithmetic operations and polynomial in overall running time (because the numbers get bigger). Here's a good implementation in Haskell: http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/fastFibonacci.hs http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/f... , and the same in Python: http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/fastFibonacci.py http://nayuki.eigenstate.org/res/fast-fibonacci-algorithms/f... . BTW, I think even functional programmers would find the Python code slightly easier to follow :-)
    - codygman 12y ago
      Maybe it's because I've been using Haskell exclusively for a few months, but I find the Haskell example more clear. This surprises me because I have much more experience with Python.
    - 12y ago
- Touche 12y ago
  > Could you suggest a simpler example? Anything that can be Googled and understood what it is trying to accomplish is less than 2 minutes. I tried Googling "sieve" and got nothing of use, then "prime sieve" that has a good wikipedia article that is (probably?) about the correct thing but doesn't fit into the "easily understood in a couple of minutes) rule. So... literally anything. Hello world. First impression shouldn't be that you need to be a math expert to use the language.
jlebar 12y ago
FWIW I think the sieve is a great example. Fibonacci is trite and a toy, whereas this is nontrivial and shows off a lot of what's powerful about Haskell (infinite lists, list comprehensions, pattern matching with cons...). It's complex enough that it encourages people to stare at it for a few minutes and engage with it, which is also good. I vote to keep it!
minikomi 12y ago
I think it's fine, but could use an "explain" link like on the http://racket-lang.org/ http://racket-lang.org/ homepage.