CIS 194: Introduction to Haskell (Spring 2013) | Hacker News Reader

CIS 194: Introduction to Haskell (Spring 2013)

cis.upenn.edu

74 pointshamidr44 comments

I really like the amount of nonsense.)

It begins with head is a mistake! It should not be in the Prelude. Other partial Prelude functions you should almost never use include tail, init, last, and (!!). From this point on, using one of these functions on a homework assignment will lose style points!

And here is a proposal:

  data NonEmptyList a = NEL a [a]

  nelToList :: NonEmptyList a -> [a]
  nelToList (NEL x xs) = x:xs

  listToNel :: [a] -> Maybe (NonEmptyList a)
  listToNel []     = Nothing
  listToNel (x:xs) = Just $ NEL x xs

  headNEL :: NonEmptyList a -> a
  headNEL (NEL a _) = a

  tailNEL :: NonEmptyList a -> [a]
  tailNEL (NEL _ as) = as

Dear sirs, a List is a recursive data structure by definition. Non-recursive List is an unimaginable nonsense. What was made here with a name of safe(!) NonEmptyList is some ugly Pair with lots of syntactic noise.

How could you get the last element from your NonEmptyList? How could you tell how many elements in it?)

But, of course, never ever use these ugly unsafe lists - they might be empty! Use safe NonEmptyList because in Haskell everything is safe. And never try to think what the fuck you are reading.

A better solution is length-encoded lists (often called Vectors):

  data Vector length a where
    Empty :: Vector 0 a
    Cons :: a -> Vector n a -> Vector (1 + n) a

But Haskell isn't very good at such encodings. Type-level computation is often not worth it.

That said, even NonEmptyList is sometimes useful. For example, some Prelude functions could use it:

  group :: [a] -> [NonEmptyList a]

Making common idioms like:

  map head . group ...

Safe again.

Not sure what you mean by:

> How could you get the last element from your NonEmptyList? How could you tell how many elements in it?) Exactly two.

  import Data.Monoid
  import Data.Maybe

  lastNel :: NonEmptyList a -> a
  lastNel (NEL x xs) = fromMaybe x . getLast $ mconcat $ map (Last . Just) xs

  lengthNel :: NonEmptyList a -> Int
  lengthNel (NEL x xs) = 1 + length xs

But these are solutions for some Array of unknown size or some abstract collection - why to call it a List? For a List the notion of the-empty-list is essential.

Not for the NonEmptyList...

Is your problem mainly what you call this notion?

I'm an old-school perfectionist, sorry.)

http://karma-engineering.com/lab/wiki/Tutorial10

If you have a structure whose only difference from a list is that it is guaranteed to have at least one element, why not call it a NonEmptyList?

I'm not quite sure what you've done there. You seem to be confusing type signatures with function definitions. You've also used GADT syntax, requiring -XGADTs, which isn't needed for a simple vector type.

> Cons :: a -> Vector n a --> Vector (1 + n) a

This makes no sense, you can't specify constants in a type signature, and you certainly can't add constants to a type variable in one.

I may be the one not in the know here, if so please show me this magic.

Not in Haskell, but there are languages where it's possible. It's called dependent typing and I don't really understand how it works, but I suppose gp was referring to this.

Oh of course, and that also explains the use of GADTs since they are one route to dependent types in Haskell. I'm not sure what he's done there is fully legit, but maybe not as loony as at first thought.

It plays fast and loose on notation, but is perfectly kosher in GHC (not Haskell2010 or Haskell98).

It is possible in GHC, see parent comment.

He used pseudo-notation for something that is possible in GHC. (1+) on type level corresponds to the successor function, and a compiling version of Peaker's code would be this:

    {-# LANGUAGE DataKinds #-}
    {-# LANGUAGE GADTs #-}
    
    data Nat = Z | S Nat
    
    data Vector l a where
          Nil :: Vector Z a
          Cons :: a -> Vector l a -> Vector (S l) a

Thanks for this! Had looked at examples of this but it's nice to have the link to Peaker's code

Yeah, I would agree that head, as it is, looks like a mistake. Instead of:

  head :: [a] -> a

I would code it as:

  head :: [a] -> Maybe a

returning Nothing for empty lists. Same applies to tail.

But others have very good reasons to disagree: http://stackoverflow.com/questions/6364409/why-does-haskells...

I don't see that answer arguing that `safeHead` is bad. Russell O'Connor just seems to be arguing that it'd not be possible for `head :: [a] -> a` to have a sentinel value `uhOh :: forall a . a` which you could pattern match on when `head []` is called... but `safeHead :: [a] -> Maybe a` is just fine since it has a different free theorem.

In the comments on Real World Haskell people (Alex Stangl and Paul Johnson in particular) are talking about added complexity of deferring invariant errors, but since these are type-declared via `Maybe` it really helps to add safety. I personally have written many, many functions with partial types because I had forgotten about some assumed invariants and had them fixed by use of `safeHead`.

NonEmptyList is pretty good for pre-handling all of the failure modes.

> Dear sirs, a List is a recursive data structure by definition.

I don't think so: http://en.wikipedia.org/wiki/List_(abstract_data_type)

NonEmptyList is usually implemented that way to be a bit lazier on the implementation end. You can also write it as

    data NEL a = One a | More a (NEL a)

but then you have to write fresh functions for all of the default list methods without any performance improvements (which make doing so totally valuable for things like Vector). You also have NEL being an instance of a more general NonEmptyFunctor pattern like in (http://hackage.haskell.org/packages/archive/non-empty/0.1.3/...).

With this recursive NEL, last is

    last :: NEL a -> a
    last (One a) = a
    last (More _ more) = last more

and (inefficient, corecursive) length is

    len :: NEL a -> Int
    len (One _) = 1
    len (More _ more) = succ (len more)

NELs are quite useful not just for safety. head as type [a] -> a is largely considered to be a mistake, the Safe package is quite popular and redefines head as having type [a] -> Maybe a. I use it frequently.

NELs have properties like being Semigroups (and not Monoids) and Comonads which regular lists do not. This helps not only for theoretical guarantees of safety but also so that we can feel confident that our typeclass declarations have the meaning they're supposed to have.

So is (NEL a = NEL a [a]) a bad solution? It's perhaps less independently beautiful than the truly recursive NEL, but it's easier to write and takes advantage of Haskell's built in "possibly empty List" functionality. It's also more "globally beautiful" in that it fits into the family of types "non-empty functors". The recursive version is also trivially isomorphic, so there's no loss in functionality.

(quick addendum: by "lazier" I meant simpler, not that either implementation of NEL is denotationally lazier than the other.)

NEL was provided as an example to think about, not as a 'proposal'. There was no suggestion that students use this for everything.

Keep in mind that this is a structured 100-level class targeted at undergrads who are relatively new to programming and haven't seen much in the way of functional programming and Hindley-Milner typing.

> List is a recursive data structure by definition

What's the justification for that assertion?

The author and teacher of this course, Brent Yorgey, is one of those rare guys who is both a fantastic lecturer and a fantastic researcher.

For Penn's fuller version of this course, check out CIS 552[1]. Dr. Stephanie Weirich is also a fantastic lecturer, and a GHC contributor to boot (IIRC).

[1] http://www.seas.upenn.edu/~cis552/12fa/

Wow, thanks for this, it's exactly what I needed.

I started from LYAH and the only thing missing from it were some exercises so I could retain the information that was presented in each chapter. Otherwise, it's a fantastic book.

I really wanted to learn functional programming when my university offered it, but unfortunately it's crunched in a horribly busy term and I'm not willing to risk core modules for it if I end up struggling.

That said, I really do want to learn it and find MOOCs a really useful tool, if anybody has any suggestions for any they've used (or the one linked, I'm unclear if that's for students at that university only) that'd be awesome!

The Wash U Programming Languages course on Coursera was pretty functional-programming oriented. I really enjoyed it and would recommend it to anyone.

Thanks, it's a shame the content is only available when it's running because again the timing isn't great. I'll definitely check it out though.

Are there any good set of videos to learn Haskell ? Or which book should I start with. I don't have much experience in Functional Programming.

you can try this out, I thought it was cute http://learnyouahaskell.com/

also this http://lisperati.com/haskell/

Start with Learn you a Haskell [1]followed by Real World Haskell[2]

[1]http://learnyouahaskell.com/

[2]http://book.realworldhaskell.org/

Yes, these videos by Eric Meijer are very good:

http://channel9.msdn.com/Series/C9-Lectures-Erik-Meijer-Func...

I believe jumping right into Haskell, unless you're already fond of recursion, is a bit too stiff. Maybe try to read SICP, it will expose you to the functional programming principles that lead to Haskell (strict vs lazy evaluation) which he mostly makes more concise and expressive.

Here's a playlist of a lecture session for HP employees by the authors of the book : http://www.youtube.com/playlist?list=PLB63C06FAF154F047

Here's the book http://mitpress.mit.edu/sicp/ ( alternate formatting texinfo http://www.neilvandyke.org/sicp-texi/ , pdf http://sicpebook.wordpress.com/ )

Er, no. If you're interested in Haskell, pick up one of the 2 mainstream Haskell books (listed in ekm2's comment) and GHC, then learn it.

SICP might be a great book, but there's a long way road from it to Haskell. If you are to read theory, then Yorgey's (the instructor for the linked course) Typeclassopedia or Okasaki's Purely Functional Data Structures will give you more bang for the buck as far as Haskell is concerned.

Alright, I can only say that in my case seeing simple recursive decomposition in scheme, macros, pattern matching (scheme, ml) then Haskell made much more sense than diving directly in Haskell very tight syntax/semantics. Without functional programming background, lazy languages with patterns can look like black magic, hence my suggestion.

I find that this rather old video from OSCON 2007 by the incredible Simon Peyton Jones (of F# and GHC) is the most inspiring Haskell video there is. It uses the X window manager XMonad as the basis to explain many important concepts of Haskell and testing (QuickCheck). It is self contained and no previous knowledge of Haskell is needed:

http://blip.tv/oreilly-open-source-convention/oscon-2007-sim...

The slides are here: http://research.microsoft.com/en-us/um/people/simonpj/papers...

I'm currently trying to learn functional programming through Haskell. Glad to have found another resource, plus this cheat sheet linked from the page looks handy: http://cheatsheet.codeslower.com/

Interesting to see a Penn site here...

Why should I learn Haskell? Will it help me professionally, or help me being a better programmer?

Yes.

You could Google that exact question. It has been answered a lot of times on StackOverflow and other sites.

Because you will find it is the best tool for many programming jobs.

Here's a few:

http://failex.blogspot.com/

http://www.haskell.org/haskellwiki/Introduction

http://fvisser.nl/post/2013/april/23/slide-cfams-talk.html

https://news.ycombinator.com/item?id=5688803

> Why should I learn Haskell?

http://stackoverflow.com/questions/1604790/what-is-haskell-a...

For my own 2-cents, once I learned QuickCheck[1] and Parsec[2], I found myself slowly rewriting them for every language I program in.

> Will it help me professionally?

Speaking as another professional, probably not.

I love Haskell, but my colleagues can't deal with it. They can't write it. They don't know functional programming. And to be entirely honest, they will never understand Monoids, Monads, or macro-hacking.

> ...Help me being a better programmer?

Maybe. If you like already like to think of software axiomatically, then yes, it will make you will make you think of software more conceptually.

But honestly, getting javascript, ruby and go under your belt will also make you think differently about software, and those are more practical languages.

[1] http://en.wikipedia.org/wiki/QuickCheck [2] http://www.haskell.org/haskellwiki/Parsec

I took this class last semester. Learned a lot. Brent was a great professor and is a great guy.

Is it only for UPENN students?

Reply on news.ycombinator.com