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