As i was going through Learn You a Haskell for Great Good , i came across following repeat function implementation : repeat' :: x - > [x] repeat' x = x : repeat' x My question is why it produces list in first place. 1:2:3 is not a list but 1:2:3:[] is. How comes haskell know that the things which we are adding will eventually added to the beginning of empty list given things are infinite so you can specify the end which is [] . Then why doing 1:3:4 is not acceptable ? Thanks Divyanshu Ranjan
On 24 June 2011 10:31, divyanshu ranjan
My question is why it produces list in first place. 1:2:3 is not a list but 1:2:3:[] is. How comes haskell know that the things which we are adding will eventually added to the beginning of empty list given things are infinite so you can specify the end which is [] . Then why doing 1:3:4 is not acceptable ?
It's quite simple if you consider that it's just based on types of expressions and nothing more. Consider the type of the (:) function: (:) :: x -> [x] -> [x] It takes x and list of x. So we can write: () : [] And the expression () : [] has type [()] Therefore we can also take that and put it on the right-hand side again: () : (() : []) See how () and (() : []) fit into the x and [x] places in the (:) function? Continuing: () : (() : (() : [])) And so on. The (:) function is right-associative (meaning x : b : c : d means x : (b : (c : d))). So we don't need the parentheses, the following is equivalent to the previous: () : () : () : [] The a:b:c syntax isn't special in any way. But you should always implicitly read it as (a:(b:c)), remembering that everything on the left-hand side of a : is type x, and everything on right-hand side is [x]. repeat' x has type [x], so you can write x : repeat x E.g. consider manually evaluating repeat () on paper, we'd write out: repeat () () : repeat () () : () : repeat () () : () : () : repeat () And so on. It will go on forever if you keep evaluating the end expression. Haskell is lazy, so we don't have to evaluate the right-hand side if we don't want use it. But the type of the expressions, you should observe, are always correct. The reason 1:3:4 is not acceptable is because 4 is not of type [x], whereas 1:3:repeat 4 would be because repeat 4 is of type [x]. Ciao!
On Friday 24 June 2011, 10:31:26, divyanshu ranjan wrote:
As i was going through Learn You a Haskell for Great Good , i came across following repeat function implementation : repeat' :: x - > [x] repeat' x = x : repeat' x My question is why it produces list in first place. 1:2:3 is not a list but 1:2:3:[] is. How comes haskell know that the things which we are adding will eventually added to the beginning of empty list given things are infinite
Well, since things are infinite here, nothing will ever be consed to an empty list. In this case, everything is consed to a nonempty list. In general, a list needs not end with [], it could also end with _|_ (bottom, undefined), 1:2:3:_|_ is a valid list, it will lead to an error/nontermination if you ever ask what comes after the 3, but if you never do that, it will work (e.g. (1:2:3:_|_) !! 2 ~> 3). The construction of repeat' goes repeat' x = x : something (where something = repeat' x, but all we need of that for the moment is that is has the correct type), so by (:) :: a -> [a] -> [a], repeat' x produces a list (if the something is a list, but something is repeat' x, which is a list, provided that something is a list, which ... So the type checker can't prove that it is a list in a finite number of deduction steps; however, it can prove that it can't be anything other than a list, and the assumption that it is a list is consistent, so it is accepted.), the first element of which is x. As long as you don't check whether the resulting list contains more than one element, nothing further is done. If you ask for further elements, the definition is entered again, each time delivering a further list element. You might look at it as a limit process, step 0: unknown step 1: x:unknown step 2: x:x:unknown step 3: x:x:x:unknown ... An equivalent (but possibly more efficient) definition is repeat'' x = let result = x : result in result
so you can specify the end which is [] .
It is not for infinite lists, you could say that infinite lists end in _|_ or that they have no end, whichever you prefer (but if you say they end in _|_, be aware that you can never reach that end).
Then why doing 1:3:4 is not acceptable ?
Because it's finite, so it has a reachable end. The end is 4, which (in general) is not a list, but a number. (If you have e.g. an instance Num [Int] where ... in scope, the 4 at the end is a valid list, whatever fromInteger does for that instance.)
Thanks Divyanshu Ranjan
participants (3)
-
Christopher Done -
Daniel Fischer -
divyanshu ranjan