0

Just struggling here with Haskell... i have a pretty bad terminology, and given my native language is not english, it's a little complicated to make the right searches :P i was following some haskell tutorials/books (Learn you a Haskell, Real World Haskell, Happy Learn Haskell, also a mailing list, and some random pages), and now i'm stopped here:

head' :: [Char] -> Char
head' (x:_) = x

This function receives a list of elements of String type, and if i apply it like this:

head' "hello"

It returns "h", which is bounded to x, and "ello" is bounded to _, but it does not matter because i don't use it. I understand that the (:) function (or used as an infix operator) receives an element which will be put and the start of a new list, whose tail will be the other received element: 'a' : ['b', 'c'] will return "abc" But, why when i use ":" inside parentheses, the first element is bounded to x and the rest to _? What happens here?

I read a few SO questions like this (x:xs) pattern Haskell logic and this (which is more closer to answer my question i think) What does (x:_) and [x:_] mean? but the accepted question of this last one says: ": is a constructor for lists, which takes the head of the new list as its left argument and the tail as its right argument. If you use it as a pattern like here that means that the head of the list you match is given to the right pattern and the tail to the left."

"The head of the list is given to the right, and the tail to the left"... it really confuses me: if the head is given to "_" and the tail to "x" when used ":" on pattern matching, why x has the value of the list head?

I think maybe its my bad english level which makes me difficult to grasp this. I will also appreciate some hint (like a specific search) instead of a direct answer.

EDIT: For another noob like me.... as said by the accepted answer, "abcd" is just 'a':'b':'c':'d', the pattern (x:_) matches 'a':'b' and so on, the underscore means "i don't care about the rest", and receives the rest of the characters. Just that :)

Micha Wiedenmann
  • 19,979
  • 21
  • 92
  • 137
Emilio Grisolía
  • 1,183
  • 1
  • 9
  • 16
  • 1
    It must be a mistake, the part to the left must match the head of the list. – Dmytro Sirenko Jul 23 '16 at 16:52
  • That was a typo. It's fixed now. – sepp2k Jul 23 '16 at 16:53
  • @EarlGray Well, i feel better now i think haha. But i still don't get it: why the tail is bounded to the _? Haskell automagically read "(x:_)" and says "well, i will bound the head to the x and the rest to _"? Or ":" when used on pattern matching between parentheses has a different meaning? Because (x:_) for my understanding is "put x at the start of _"... This may be a silly question, sorry :) – Emilio Grisolía Jul 23 '16 at 16:59
  • @sepp2k Thanks to you too man :) – Emilio Grisolía Jul 23 '16 at 17:00
  • `:` in the function definition is not an application, it's syntactic sugar called _pattern matching_, that takes a concrete value of type `[String]`, checks if it can be described by pattern `(x:_)` and if it is the case, takes the head of the list and names it `x`, throwing away the rest (`_`). If there are no matching function definitions, a runtime exception is thrown. – Dmytro Sirenko Jul 23 '16 at 17:02
  • @EarlGray Thanks for your time! It really helped me :) – Emilio Grisolía Jul 23 '16 at 17:57
  • 2
    @EarlGray, in Haskell, pattern matching is most definitely *not* syntactic sugar. It is instead the most fundamental way to inspect data. In fact, pattern matches in Haskell are compiled into pattern matches in GHC's intermediate language and survive right up until code generation! `if/then/else` forms and guards *are* syntactic sugar, and compile to pattern matches. – dfeuer Jul 24 '16 at 05:45
  • Yes, I was wrong about its role, it's a mechanism that percolate the compilation pipeline deeply, not just desugaring. My point is that it is translated into sophisticated run-time code that does many useful things efficiently. – Dmytro Sirenko Jul 24 '16 at 16:42

1 Answers1

8

The list data type is defined like this:

data [a] = [] | a : [a]

That means that a list of as is either empty, or a head element attached to a tail element using the : (cons) constructor.

When you pattern match on a list, you define your function for each of these two cases. In the case of head', it just fails when given an empty list, so we only match one case: the a : [a] case.

If you called head' "hello" (as it exists right now, with the type signature included) it should fail, because "hello" is actually a String -- an alias for [Char] in Haskell. "hello" is merely syntactic sugar for the following construction:

"hello" = 'h':'e':'l':'l':'o':[]

So, when you pattern match on the list using head', you get 'h' on the left side of the first :, and the rest of the list (which we don't care about) bound to _.

Benjamin Kovach
  • 3,190
  • 1
  • 24
  • 38
  • Type signature had a typo, i have the original code in my pc, so i didn't copy-pasted it. It's fixed now, sorry :) – Emilio Grisolía Jul 23 '16 at 17:31
  • After some coding and re-reading your question and EarlGray's, i think i understand it :) thank you very much man. I really appreciate your help :) – Emilio Grisolía Jul 23 '16 at 17:56
  • How is `data [a] = [] | a : [a]` valid? I'm unable to do something like that in ghci: `data TestType = Integer | Integer : [Integer]` – Lance Clark Feb 22 '18 at 16:20
  • 1
    @LanceClark Lists are special, the language (well, GHC) handles this particular definition for you. You can redefine an isomorphic type, though, like this: `data List a = Nil | Cons a (List a)` – Benjamin Kovach Feb 22 '18 at 21:23