7 ms·

Haskell tutorial for C programmers

177 points by foulas 12y ago

austinz 12y ago
This is great, and I've bookmarked it for reference while reading LYAH. Thanks for writing it. For anyone who needs a refresher on DFA, Stanford's CS143 compilers class course materials are up on Coursera (https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers), and pretty helpful.
giuscri 12y ago
Uhm ...great perspective!
im3w1l 12y ago
>What this means is that existing sort functions such as mergeSort and quickSort would need to be rewritten to sort values of the new type. In constrast, here is the type of mergeSort in Haskell mergeSort :: Ord a => [a] -> [a] Er, you could define mergesort using templates in c++ and it would work pretty much the same.
- DannoHung 12y ago
  How do you express the Ordinality constraint in C++?
  - GeneralMayhem 12y ago
    Multiple inheritance from a purely virtual class. In Java, they're called interfaces; Comparable is the analogue to Ord. The advantage that Haskell's typeclasses have over either Java or C++ is that the types aren't closed. I can define a new typeclass and tell the compiler that a type you defined is a member of that class at any point. In Java, if you don't define that your type is Comparable, there's nothing that I, as a consumer of your type, can do about it.
    - chongli 12y ago
      Yeah, though you will want to be the owner of either the type class or the type itself. Instances which are neither are called orphan instances and they are generally frowned upon. Luckily, it's trivial to create a newtype wrapper which gives you a whole new set of hooks for writing instances of a type.
      - dllthomas 12y ago
        Orphan instances in libraries are frowned upon. In an application they are more palatable, though a newtype might still be a better choice, depending.
      - GeneralMayhem 12y ago
        That makes sense, but again, in Java you can't do it if you're just the owner of the typeclass, and in order to make a wrapper you'd have to make a subclass, which mucks with all kinds of other things.
    - Peaker 12y ago
      The advantage you mention is one of many (over OOP interfaces), I'll repeat it as (A). (A) Ability to instantiate old types with new classes (B) Conditional instantiation: "Maybe a" is an instance of "Show" iff "a" is an instance of "Show" (C) Can do return-type polymorphism, or polymorphism on any part of the signature (D) Objects do not need to pay for the interface vtable pointer. Large array of some type-class instance can be much smaller than an array of an OOP interface subclass. (E) When comparing two Ord instance values, there is only one Ord dictionary, rather than 2 to choose from. No false dilemma.
      - GeneralMayhem 12y ago
        (C) is covered by generics in most cases. The others, yes.
        judk 12y ago
        Generics aren't ad-hoc polymorphic. Type classes are.
  - cozmorado 12y ago
    Concepts will accomplish this when they finally make it into the standard.
    - pbsd 12y ago
      Concepts will certainly be nice once they arrive in the standard, but it is already possible today with some trickery. Example checking whether an std::vector<T>'s type is comparable with `operator<`: http://coliru.stacked-crooked.com/a/2ea46e0afd894d3d http://coliru.stacked-crooked.com/a/2ea46e0afd894d3d The error you get if you try to sort a vector with an unordered type is relatively easy to read: main.cpp: In instantiation of 'void merge_sort(std::vector<_RealType>&) [with T = type]': main.cpp:45:17: required from here main.cpp:30:5: error: static assertion failed: Element type is not sortable static_assert( concept::is_ord<T>(), "Element type is not sortable" ); ^
  - Rusky 12y ago
    The existence of an operator< or the existence of a template specialization. Not as nice, and incapable of runtime polymorphism, but that's typically how it's done. Concepts would have been more explicit about it but they're also compile-time only. Interfaces or pure virtual classes are not the same because they're closed.
- GFK_of_xmaspast 12y ago
  Yeah, I don't get why that's superior to something like std::sort : http://en.cppreference.com/w/cpp/algorithm/sort http://en.cppreference.com/w/cpp/algorithm/sort (or a similar approach however you like).
  - acomar 12y ago
    The difference is entirely in the types. A sort function in Haskell has type: Ord a => [a] -> [a] You therefore know that the implementation of the function can only make use of functions provided by Ord, and manipulation of the list structure. The function cannot inspect the values in the list except via comparison. This is an incredibly powerful guarantee. It's also really useful when you go to implement the function because this level of parametricity guarantees that there are only so many valid implementations and only a couple of them are even close to correct.
    - millstone 12y ago
      All true. On the other hand, std::sort in C++ works on RandomAccessIterator, which means that it can sort vectors, C arrays, deques, strings, your custom container type, etc. The Haskell implementation can only sort lists. Furthermore, the Haskell type signature fails to express that the input and output have the same size. But std::sort necessarily preserves its size, because you pass it a range, and a range cannot access its underlying container to change its size (a limitation leading to bizarre APIs like std::unique).
      - Peaker 12y ago
        You can define a mutable std::sort like function in Haskell: mutableSort :: (MArray arr elem m, Ord elem, Ix ix) => arr ix elem -> m () This can work on mutable arrays in the IO, ST, or other mutable-array supporting monads. It also has a generalized index type (though newer array libraries threw that part away, so it's not considered a good idea anymore).
Kiro 12y ago
Great! A Haskell tutorial for JS or PHP programmers would be awesome.
- tosinaf 12y ago
  Or you could try being functional in JS, there are some good resources on that.
  - judk 12y ago
    An statically typed JS environments with type inference and laziness?
- tinco 12y ago
  How would it be different? JS and PHP are near identical to C.
  - judk 12y ago
    How do I port closure-heavy prototype-based objects from JS to Haskell? This isn't near identical to C.
deleted 12y ago
[deleted]
vendakka 12y ago
This makes for very good reading indeed. I started reading it and just now realised that I'd spent the last couple of hours on it. It's written well, approachable and very pragmatic. I spent a short while on Haskell a few years back and stopped after 3 or 4 chapters of Learn You A Haskell due to time constraints. I think I'm going to make this my evening reading and finally pick up the language. Thanks for posting this. EDIT: typos
- Peaker 12y ago
  That's great! Don't expect to "pick up the language" in an evening :) Haskell takes a few evenings at the very least!
cgag 12y ago
Chris Allen / coolsunglasses maintains a great gist of a learning path for haskell: https://gist.github.com/bitemyapp/8739525 https://gist.github.com/bitemyapp/8739525 The current intro course looks really nice: http://www.seas.upenn.edu/~cis194/lectures.html http://www.seas.upenn.edu/~cis194/lectures.html
- akurilin 12y ago
  That gist is a fantastic resource, strongly endorsed.
- nardi 12y ago
  This gist was what helped me finally learn Haskell, after failing on my first two tries.
kahaw 12y ago
This is great, now I just need a similar tutorial but for LISP.
- CyberShadow 12y ago
  Here's an interactive one: http://www.eblong.com/zarf/zweb/lists/ http://www.eblong.com/zarf/zweb/lists/ Bit dated, though :)
kisstheblade 12y ago
Was hopeful but almost immediately this article also devolved into introducing the fibonacci function. This is almost as bad as examples of "aspect oriented programming" in java 10 years ago when every example involved inserting logging aspects to your code... Just write a simple tutorial about a real world example, nowadays usually having something to do with the web, and especially point out how it's better than doing the same thing in ruby, php or even gasp java! We'll learn ourselves how you define lists and how magical they are in haskell... And people who write compilers and parses all day long probably won't have a problem with the way haskell looks.
cnvogel 12y ago
Oh my, another tutorial. I've looked at many of them, trying to learn something from the Haskell way. And I think I get the fundamental advantages of the type systems, the lazy evaluation enabled by the languages purity, I think I can somehow make sense of the Monads even. I have the "learn you a haskell for good" on a pile of books where I have a glimpse from time to time. Most tutorials and books are very enthusiastic in how they can detect that I try to zip two lists of different cardinality during compile time, or how they can lazily calculate the Fibbonacci sequence. And that's really nice and fine... But nevertheless, I use C all of the time, and I learnt how to make use of a myriad of libraries, combine connections to a SQL database, embedd a webserver, talk to USB,... Must have been 20 years ago that I wrote code to calculate the Fibbonacci sequence. So, where are tutorials that showcase all the wonderful "high-level" functionality that has already been written for Haskell, so that I, after reading through the text, will be thrilled how much work I can avoid, or how much security I can gain when switching over from my "almost bare-matel not-much-more-like-an-assembler C" to Haskell? Not in calculating the Fibunacci sequency, but in writing a backend for my web-app, or talk to a USB peripheral? Do 3D graphics?...
- Dewie 12y ago
  These kinds of questions feels like they're treading the fine line between being honest inquiries, and dares.
  - cnvogel 12y ago
    Of course you don't have to believe me, but I'm genuinely puzzled why apparently most tutorials spend such an disproportionate amount on these more theoretical explanations. One explanation of course might be that a lot of the crowd looking into this are coming from a computer-science background where they are more enthusiastic about the basics. And to them, the fact that (after a lot of coding chores, writing up libraries) it eventually will make sql-injection harder, or parallel handling of web-service faster will be seen just as a logical consequence not worth making a lot of fuzz about. But for attracting a larger community one has to make the gains for the average programmer more visible.
- 12y ago
rfrey 12y ago
@kissthblade: Your comment (dead) below is very sad. You've been hell-banned for more than a year and a half. It doesn't just seem like nobody is seeing your comments, it's true. For those without showdead on: "I posted about the same comment as the parent hours ago. I don't know if anybody even sees my posts, never gotten a response, and my "karma" or something has always been 15. And posting and reading the forum is very slow. What gives?" Looking through your comments, I don't see an obvious reason you were hellbanned.
- consz 12y ago
  This happened to me, too. I spent about a year replying before finally seeing someone mention I was hell banned. I also wondered why the forum was so slow, but it's not particularly well coded so I just assumed its always been like that.
- judk 12y ago
  This is why it is important to use a different account on each of your browsing devices, with [showdead] so you can see of you got hellbanned. But I guess if you can do that, you would also recognize the effects of a hellban on your account.
- TuringTest 12y ago
  Is that something common at Hacker News? I find it worrisome that someone can be banned from a community and not even be aware of it. What's the point of punishing wrong behavior if the one making it isn't aware that it was wrong? I'm trying to grasp how moderation and banning works around here, but it's difficult since neither the FAQ nor the posting guidelines have an explanation about it.

177 points by foulas 12y ago

This is great, and I've bookmarked it for reference while reading LYAH. Thanks for writing it. For anyone who needs a refresher on DFA, Stanford's CS143 compilers class course materials are up on Coursera (https://www.coursera.org/course/compilers https://www.coursera.org/course/compilers), and pretty helpful.

giuscri 12y ago

Uhm ...great perspective!

im3w1l 12y ago

>What this means is that existing sort functions such as mergeSort and quickSort would need to be rewritten to sort values of the new type. In constrast, here is the type of mergeSort in Haskell mergeSort :: Ord a => [a] -> [a] Er, you could define mergesort using templates in c++ and it would work pretty much the same.

DannoHung 12y ago
How do you express the Ordinality constraint in C++?
- GeneralMayhem 12y ago
  Multiple inheritance from a purely virtual class. In Java, they're called interfaces; Comparable is the analogue to Ord. The advantage that Haskell's typeclasses have over either Java or C++ is that the types aren't closed. I can define a new typeclass and tell the compiler that a type you defined is a member of that class at any point. In Java, if you don't define that your type is Comparable, there's nothing that I, as a consumer of your type, can do about it.
  - chongli 12y ago
    Yeah, though you will want to be the owner of either the type class or the type itself. Instances which are neither are called orphan instances and they are generally frowned upon. Luckily, it's trivial to create a newtype wrapper which gives you a whole new set of hooks for writing instances of a type.
    - dllthomas 12y ago
      Orphan instances in libraries are frowned upon. In an application they are more palatable, though a newtype might still be a better choice, depending.
    - GeneralMayhem 12y ago
      That makes sense, but again, in Java you can't do it if you're just the owner of the typeclass, and in order to make a wrapper you'd have to make a subclass, which mucks with all kinds of other things.
  - Peaker 12y ago
    The advantage you mention is one of many (over OOP interfaces), I'll repeat it as (A). (A) Ability to instantiate old types with new classes (B) Conditional instantiation: "Maybe a" is an instance of "Show" iff "a" is an instance of "Show" (C) Can do return-type polymorphism, or polymorphism on any part of the signature (D) Objects do not need to pay for the interface vtable pointer. Large array of some type-class instance can be much smaller than an array of an OOP interface subclass. (E) When comparing two Ord instance values, there is only one Ord dictionary, rather than 2 to choose from. No false dilemma.
    - GeneralMayhem 12y ago
      (C) is covered by generics in most cases. The others, yes.
      - judk 12y ago
        Generics aren't ad-hoc polymorphic. Type classes are.
- cozmorado 12y ago
  Concepts will accomplish this when they finally make it into the standard.
  - pbsd 12y ago
    Concepts will certainly be nice once they arrive in the standard, but it is already possible today with some trickery. Example checking whether an std::vector<T>'s type is comparable with `operator<`: http://coliru.stacked-crooked.com/a/2ea46e0afd894d3d http://coliru.stacked-crooked.com/a/2ea46e0afd894d3d The error you get if you try to sort a vector with an unordered type is relatively easy to read: main.cpp: In instantiation of 'void merge_sort(std::vector<_RealType>&) [with T = type]': main.cpp:45:17: required from here main.cpp:30:5: error: static assertion failed: Element type is not sortable static_assert( concept::is_ord<T>(), "Element type is not sortable" ); ^
- Rusky 12y ago
  The existence of an operator< or the existence of a template specialization. Not as nice, and incapable of runtime polymorphism, but that's typically how it's done. Concepts would have been more explicit about it but they're also compile-time only. Interfaces or pure virtual classes are not the same because they're closed.
GFK_of_xmaspast 12y ago
Yeah, I don't get why that's superior to something like std::sort : http://en.cppreference.com/w/cpp/algorithm/sort http://en.cppreference.com/w/cpp/algorithm/sort (or a similar approach however you like).
- acomar 12y ago
  The difference is entirely in the types. A sort function in Haskell has type: Ord a => [a] -> [a] You therefore know that the implementation of the function can only make use of functions provided by Ord, and manipulation of the list structure. The function cannot inspect the values in the list except via comparison. This is an incredibly powerful guarantee. It's also really useful when you go to implement the function because this level of parametricity guarantees that there are only so many valid implementations and only a couple of them are even close to correct.
  - millstone 12y ago
    All true. On the other hand, std::sort in C++ works on RandomAccessIterator, which means that it can sort vectors, C arrays, deques, strings, your custom container type, etc. The Haskell implementation can only sort lists. Furthermore, the Haskell type signature fails to express that the input and output have the same size. But std::sort necessarily preserves its size, because you pass it a range, and a range cannot access its underlying container to change its size (a limitation leading to bizarre APIs like std::unique).
    - Peaker 12y ago
      You can define a mutable std::sort like function in Haskell: mutableSort :: (MArray arr elem m, Ord elem, Ix ix) => arr ix elem -> m () This can work on mutable arrays in the IO, ST, or other mutable-array supporting monads. It also has a generalized index type (though newer array libraries threw that part away, so it's not considered a good idea anymore).

Kiro 12y ago

Great! A Haskell tutorial for JS or PHP programmers would be awesome.

tosinaf 12y ago
Or you could try being functional in JS, there are some good resources on that.
- judk 12y ago
  An statically typed JS environments with type inference and laziness?
tinco 12y ago
How would it be different? JS and PHP are near identical to C.
- judk 12y ago
  How do I port closure-heavy prototype-based objects from JS to Haskell? This isn't near identical to C.

deleted 12y ago

[deleted]

vendakka 12y ago

This makes for very good reading indeed. I started reading it and just now realised that I'd spent the last couple of hours on it. It's written well, approachable and very pragmatic. I spent a short while on Haskell a few years back and stopped after 3 or 4 chapters of Learn You A Haskell due to time constraints. I think I'm going to make this my evening reading and finally pick up the language. Thanks for posting this. EDIT: typos

Peaker 12y ago
That's great! Don't expect to "pick up the language" in an evening :) Haskell takes a few evenings at the very least!

cgag 12y ago

Chris Allen / coolsunglasses maintains a great gist of a learning path for haskell: https://gist.github.com/bitemyapp/8739525 https://gist.github.com/bitemyapp/8739525 The current intro course looks really nice: http://www.seas.upenn.edu/~cis194/lectures.html http://www.seas.upenn.edu/~cis194/lectures.html

akurilin 12y ago
That gist is a fantastic resource, strongly endorsed.
nardi 12y ago
This gist was what helped me finally learn Haskell, after failing on my first two tries.

kahaw 12y ago

This is great, now I just need a similar tutorial but for LISP.

CyberShadow 12y ago
Here's an interactive one: http://www.eblong.com/zarf/zweb/lists/ http://www.eblong.com/zarf/zweb/lists/ Bit dated, though :)

kisstheblade 12y ago

Was hopeful but almost immediately this article also devolved into introducing the fibonacci function. This is almost as bad as examples of "aspect oriented programming" in java 10 years ago when every example involved inserting logging aspects to your code... Just write a simple tutorial about a real world example, nowadays usually having something to do with the web, and especially point out how it's better than doing the same thing in ruby, php or even gasp java! We'll learn ourselves how you define lists and how magical they are in haskell... And people who write compilers and parses all day long probably won't have a problem with the way haskell looks.

cnvogel 12y ago

Oh my, another tutorial. I've looked at many of them, trying to learn something from the Haskell way. And I think I get the fundamental advantages of the type systems, the lazy evaluation enabled by the languages purity, I think I can somehow make sense of the Monads even. I have the "learn you a haskell for good" on a pile of books where I have a glimpse from time to time. Most tutorials and books are very enthusiastic in how they can detect that I try to zip two lists of different cardinality during compile time, or how they can lazily calculate the Fibbonacci sequence. And that's really nice and fine... But nevertheless, I use C all of the time, and I learnt how to make use of a myriad of libraries, combine connections to a SQL database, embedd a webserver, talk to USB,... Must have been 20 years ago that I wrote code to calculate the Fibbonacci sequence. So, where are tutorials that showcase all the wonderful "high-level" functionality that has already been written for Haskell, so that I, after reading through the text, will be thrilled how much work I can avoid, or how much security I can gain when switching over from my "almost bare-matel not-much-more-like-an-assembler C" to Haskell? Not in calculating the Fibunacci sequency, but in writing a backend for my web-app, or talk to a USB peripheral? Do 3D graphics?...

Dewie 12y ago
These kinds of questions feels like they're treading the fine line between being honest inquiries, and dares.
- cnvogel 12y ago
  Of course you don't have to believe me, but I'm genuinely puzzled why apparently most tutorials spend such an disproportionate amount on these more theoretical explanations. One explanation of course might be that a lot of the crowd looking into this are coming from a computer-science background where they are more enthusiastic about the basics. And to them, the fact that (after a lot of coding chores, writing up libraries) it eventually will make sql-injection harder, or parallel handling of web-service faster will be seen just as a logical consequence not worth making a lot of fuzz about. But for attracting a larger community one has to make the gains for the average programmer more visible.
12y ago

rfrey 12y ago

@kissthblade: Your comment (dead) below is very sad. You've been hell-banned for more than a year and a half. It doesn't just seem like nobody is seeing your comments, it's true. For those without showdead on: "I posted about the same comment as the parent hours ago. I don't know if anybody even sees my posts, never gotten a response, and my "karma" or something has always been 15. And posting and reading the forum is very slow. What gives?" Looking through your comments, I don't see an obvious reason you were hellbanned.

consz 12y ago
This happened to me, too. I spent about a year replying before finally seeing someone mention I was hell banned. I also wondered why the forum was so slow, but it's not particularly well coded so I just assumed its always been like that.
judk 12y ago
This is why it is important to use a different account on each of your browsing devices, with [showdead] so you can see of you got hellbanned. But I guess if you can do that, you would also recognize the effects of a hellban on your account.
TuringTest 12y ago
Is that something common at Hacker News? I find it worrisome that someone can be banned from a community and not even be aware of it. What's the point of punishing wrong behavior if the one making it isn't aware that it was wrong? I'm trying to grasp how moderation and banning works around here, but it's difficult since neither the FAQ nor the posting guidelines have an explanation about it.