News for hackers. Stuff that matters.
Re:The New Haskell Homepage by gamegoblin on Wednesday July 09, 2014 @02:04AM (#8008287)
Ok I'll take a stab at a super high level crash course:

A note! Haskell has weird syntax. But it actually uses this syntax in cool ways, as opposed to some languages that have weird syntax in an effort to be different.

Let's consider the basic unit of Haskell programming -- the function!

Here is a function which returns its input:

    f x = x
Notice that there are no parens or types or anything. Since functions are used so heavily, polluting them with parens would make your code look uglier than lisp.

Now notice that I didn't include a type signature. In haskell, you can omit them if you want. The compiler will figure out the most general type. Think of this as C++11 `auto` keyword on steroids.

If I were to include the type signature, it would look like this:

    f :: a -> a
    f x = x
Let's break down those symbols.

`::` just means "is of the type". So `f :: ...` is "function f is of the type..."

`a` is a type variable. Think of this like C++ templates! In C++, an equivalent function is

   template <typename T>
   T f(T x) { return x; }
Where `T` is the same as our `a` in Haskell. In Haskell, it's common to use the first few letters of the alphabet for type variables.

The `->` syntax is a bit funny, but it makes sense when you learn about function currying, which I will not explain now because it can be intimidating to some. For now, just think of the type signature as

    arg1Type -> arg2Type -> ... -> argNType -> ResultType
So for our function `f` of type

    f :: a -> a
That means "The function f takes some argument of type `a`, and returns a value of the same type `a`"

Now let's consider a more complex function.

    f x = 2 * x
As you can see, this is a doubling function. It takes a value and doubles it. We can imagine that the value it takes can't be any arbitrary type, because not all types can be doubled! So it doesn't make much sense to pass in a string.

In Java style, we might say that the type must implement the interface `Multipliable` or something. It turns out, Haskell has a system that is very roughly similar to Java interfaces or in C++, a class with a bunch of virtual methods.

Haskell calls these Typeclasses. So there is a typeclass that specifies that types in the typeclass must implement some basic numeric methods, such as +, -, etc. This typeclass is called `Num`.

So we can imagine, our doubling function only takes types that implement `Num`. Our type signature reads:

    f :: Num a => a -> a
    f x = x * 2
So everything between the :: and the => is typeclass specifications. So in this one, I just specify that type `a` must implement `Num`. Let's say I also required `a` to have the equivalent of a Java `toString` method, I would say:

    f :: (Show a, Num a) => a -> a
So now `a` must have a `toString` style method and must have numeric methods.

Now we are ready to approach the `primes` bit.

The first foreign looking thing is [2..]. This is an infinite list from 2 to infinity. How can one have an infinite list? The answer is laziness.

Whenever I go and ask for the 10000th value, the list must extend itself to that value if it hasn't yet. So the list only grows for as much as you ask for, but in theory it will grow until you run out of memory.

The [m..n] syntax is just nice syntactic sugar because it's used so much. [1..10] == [1,2,3,4,5,6,7,8,9,10]

[1..] == [1,2,3,4,5,....infinity]

So this is what we know so far:

    primes = sieve [2..]
Which means "primes is equal to the function sieve, called on an infinite list from 2 to infinity"

Now you ask, well what the hell is the function `sieve`?

Haskell has a nice sugar for defining scoped functions within other functions with the `where` keyword.

Consider the doubling function. I could instead do:

    f x = x * (three - one)
      where
        three = 3
        one = 1
So it just let's you define values that get used in the function body in a convenient place. This is akin to math jargon where people say "blah blah x something blah where x is blah".

So `sieve` is a scoped function (cannot be accessed from outside of `primes` that takes a list as an argument and apparently produces the primes that are in that list. How does it do it?

We see some weird syntax in the definition of `sieve`:

    sieve (p:xs) = ...
What is this? It's pattern matching. Let me use fake C++ as an example. Consider the recursive factorial function:

    int fact(int n) {
        if(n == 0) return 1;
        return n * fact(n-1);
    }
Now imagine if C++ let you do this instead:

    int fact(0) { return 1; }
    int fact(int n) { return n * fact(n-1); }
That is, you make a special case function body when the argument is 0. At runtime, if the arg is 0, it uses the special case body, otherwise it falls through to the general body.

So in Haskell, we could implement factorial like

    fact :: Num a => a -> a
    fact 0 = 1
    fact n = n * fact (n-1)
Very clean and sexy! But now you say "Yeah, but I could just use an if statement or a switch..."

Now we go into the funny syntax and power of that funny syntax! Not only can pattern matching match on values, but it can decompose those values. What do I mean? Again, let me use some fake C++ as an example.

Consider the C++ function

    int f(pair<int, int> my_pair) {
        int x = my_pair.first;
        int y = my_pair.second;
        return x*y;
    }
Ignore that there is no real reason to pull the values out into `x` and `y`. In a more complex function, I'm sure you can understand why it would be tedious to type `my_pair.first` over and over again and we would want to pull it into `x` or something.

Now imagine if C++ let us do this:

    int f(pair<x, y>) {
        return x*y;
    }
That is, f takes a pair, and in the type declaration we decompose the pair into its first and second parts, assigning them to the variables `x` and `y`. In Haskell, this is trivial.

Consider a direct translation of the C++:

    f :: (Int, Int) -> Int
    f my_pair = fst my_pair * snd my_pair
Now the idiomatic Haskell, with pattern matching decomposition:

    f :: (Int, Int) -> Int
    f (x,y) = x*y
Slick, right?

So what is `sieve (p:xs)` decomposing?

In Haskell, the default [] list is a linked list (there are random access arrays in various libraries). That means we can stick a value onto the front of the list in O(1) time. The way we stick a value onto the front of the list is with the `:` operator.

So

    x = [1,2,3]
    y = 0:x
`y` is now [0,1,2,3]

Just like we can compose lists with the `:` operator, we can decompose them via pattern matching with it.

So consider the function (I'll omit the type signature for brevity)

    f (p:xs) = print (p, xs)
Let's say we give `f` the argument [1,2,3,4]. What call to `:` would we have to make to get this list?

    [1,2,3,4] == 1:[2,3,4]
So when we send [1,2,3,4] into `f`, it gets decomposed into ` 1:[2,3,4] ` where 1 gets put into `p` and [2,3,4] gets put into `xs`.

This is a very common idiom in Haskell. Let's say I wanted to make a function that added 1 to every value in a list. Ignoring that there are much cooler/efficient ways to do this in Haskell, let's make a specialized function for it.

    addOne (x:xs) = x+1 : addOne xs
So let's read through that. In our pattern matching decomposition, we pull off the first value of the list and store it in `x`, and we take the rest of the list and store it in `xs`.

Now in our function body, we recompose a list with different values. Those values are `x+1` for the first value, and `addOne xs` for the second value. So we add one to the first value, and stick it into the front of the rest of the list after the rest has had 1 added to its values. You might notice now, that there is no bottom-out case for this recursion. So let's add one.

    addOne [] = []
    addOne (x:xs) = x+1 : addOne xs
So we pattern match to catch the special case of the empty list, which returns the empty list, and then we decompose the general case as previously explained.

So `sieve` is pulling off the first value, storing it in `p`, and taking the rest of the list and storing it in `xs`.

It is returning...

    p : sieve [x | x <- xs, x `mod` p /= 0]
So, that is `p` stuck onto the front of...

    sieve [x | x <- xs, x `mod` p /= 0]
And we know that sieve returns all of the primes within its argument, so in English...

    p stuck onto the front of all the primes in [x | x <- xs, x `mod` p /= 0]
So now what the hell is [x | x <- xs, x `mod` p /= 0]? It is a list comprehension.

Hackernews said my comment was too long. Read the rest here: http://pastebin.com/UesYMjjJ

Re:The New Haskell Homepage by codygman on Wednesday July 09, 2014 @02:46AM (#8008388)
Wow, you should turn this into a tutorial on FPComplete or something. Maybe there could be an "explain" link under the Haskell example on the homepage and it link to a tutorial like this one.
Re:The New Haskell Homepage by gamegoblin on Wednesday July 09, 2014 @02:52AM (#8008398)
I'm actually recoding my website right now with a webserver and framework I custom built in Haskell. Maybe I'll make some of my first posts on this topic in a more formal, less commenty manner.
Re:The New Haskell Homepage by dbenamy on Wednesday July 09, 2014 @04:06AM (#8008560)
But the commenty style is awesome!
Re:The New Haskell Homepage by moomin on Wednesday July 09, 2014 @04:04AM (#8008557)
Do, this thing needs a more permanent home.
Re:The New Haskell Homepage by mkesper on Thursday July 10, 2014 @03:11AM (#8014001)
What is pattern matching really used for? The way it's presented in these examples it feels like a complicated version of Python slicing.
Re:The New Haskell Homepage by gamegoblin on Thursday July 10, 2014 @04:34AM (#8014190)
Well, you can use it to match on any value. So it's more useful than just slicing up lists.

Python has a primitive form of pattern matching in the form of unpacking, for example, this is legal code:

    def tuple_decomp( (a,b) ):
        return a+b
You pass in a 2-tuple (1,2) and 1 gets put into `a` and 2 gets put into `b`. It will error on anything but a 2-tuple.

As I showed in my examples, which I think you might have overlooked if you only saw the list slicing example, it provides a nice way of writing base cases for recursive functions:

    factorial 0 = 1
    factorial n = n * factorial (n-1)
as opposed to

    factorial n = if n == 0 
                    then 1
                    else n * factorial (n-1)
It's also really useful if you have a special case that you can provide a better implementation for:

    multiply 0 _ = 0
    multiply _ 0 = 0
    multiply n m = n * m
The _ means "ignore this argument, I won't use it". So in the case that either arg is 0, we just fast-fail and return 0. Since Haskell is lazy, if I say

    multiply (f (g (h 999))) 0
where f(g(h 999))) is going to be some huge time consuming computation, the call will return instance because it will see the 0 and never even evaluate the first argument.

In C et al, the arguments to a function are evaluated before they are passed in, so if I say

    multiply( f(g(h(999))), 0);
It will calculate the value of f(g(h(999))) and send it in. In Haskell, you just send in a sort of pointer which points to the unevaluated expression, which, if you ask for it, will be evaluated.

Using pattern matching for decomposition is particularly useful in Haskell because of the custom datatypes. In Haskell, you can sort-of think of a data type as a C-union of C-structs. Let's say I define a datatype for Pets.

    data Pet = 
        Cat {
            color :: String,
            breed :: String,
            annoying :: Bool
        } |
        Dog {
            breed :: String,
            trained :: Bool
        }
So I can make a Cat or a Dog, but both are still of type Pet. They contain different parameters within them. So I can't ask a Cat if it's trained, and I can't ask a Dog if it's annoying.

Let's say I want to make a function to determine if I like a pet. My criteria are: I only like trained dogs. If a Dog is trained, I like it. As for cats, I like it if it is not annoying, or if it is Yellow.

Rather than a mess of if statements, it's much more elegant to use pattern matching!

    likePet (Cat "Yellow" _ _) = True
    likePet (Cat _ _ False) = True
    likePet (Cat _ _ _) = False
    likePet (Dog _ True) = True
    likePet (Dog _ _) = False
So as you can see, I can pattern match on constructors (Cat or Dog), and on the values within the types without putting any code in the actual function body! Compare that code to the same code with if statements and tell me which is prettier!
Re:The New Haskell Homepage by mkesper on Friday July 11, 2014 @08:23AM (#8019763)
Highly interesting, thanks!
Re:The New Haskell Homepage by forrestthewoods on Wednesday July 09, 2014 @02:13AM (#8008307)
Thanks for the reply. Some good stuff there. Very meaty and it's gonna take time plus a few read through a to chew through it all. Thanks!
Re:The New Haskell Homepage by feelix on Wednesday July 09, 2014 @02:46AM (#8008387)
The way I'd be interested in seeing a high level introduction would be by having some snippets of code in C, and then their equivalents of Haskell. Then an explanation, if that's needed. Because otherwise I'm spending most the time trying to understand what the code examples you wrote actually do in English.
Re:The New Haskell Homepage by Kiro on Wednesday July 09, 2014 @03:54AM (#8008533)
Best syntax explanation I've ever read. Awesome! You should write a book.
Re:The New Haskell Homepage by visarga on Wednesday July 09, 2014 @11:31AM (#8010166)
Thank you a lot. It was useful grok me some Haskell.