<div dir="ltr"><div><div><div><div><div><div><div>@Rein:<br></div>Perhaps I should have been a bit more clear. There is no way to get a terminal value from said function. <br><br><br>oddsFrom3 :: [Integer]<br> oddsFrom3 = map (+2) oddsFrom3<br><br></div>Try a head for it perhaps.<br><br></div>oddsFrom3 = map (+2) oddsFrom3<br></div><=> ((head oddsFrom3) + 2) : map (+2) ((tail oddsFrom3) + 2)<br></div><=> ((head (map (+2) oddsFrom3) + 2) : map (+2) ((tail oddsFrom3) + 2)<br><br></div>Sure, it doesn't hang until you try to evaluate this (in lazy language evaluators). However, for any inductive structure, there needs to be a (well any finite number of terminals) terminal (base case) which can be reached from the starting state in a finite amount of computational (condition for termination). Type sigs don't/can't guarantee termination. If they don't have a terminal value, you'll never get to the bottom (bad pun intended) of it.<br><br></div><div><br>Take an infinite list as an example.<br></div><div><br>x a = a : x a<br></div><div><div><div><div><div><div><br></div><div>Here, one branch of the tree (representing the list as a highly unbalanced tree where every left branch is of depth one at any given point). If such a structure is not present, you can never compute it to a value and you'll have to infinitely recurse.<br><br></div><div>Try x a = x a ++ x a<br><br></div><div>And think of the getting the head from this. You're stuck in an infinite loop.<br><br></div><div>You may also think of the above as a small BNF and try to see if termination is possible from the start state. A vaguely intuitive way of looking at it for me, but meh, I might be missing something.<br></div><div><br></div><div><br></div></div></div></div></div></div><div class="gmail_extra"><br><div class="gmail_quote">On Mon, Aug 17, 2015 at 10:23 PM, Rein Henrichs <span dir="ltr"><<a href="mailto:rein.henrichs@gmail.com" target="_blank">rein.henrichs@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><span class="">> <span style="font-size:13.1999998092651px;line-height:19.7999992370605px">The initial version which the OP posted doesn't have a terminal value. </span><div><span style="font-size:13.1999998092651px;line-height:19.7999992370605px"><br></span></div></span><div><span style="font-size:13.1999998092651px;line-height:19.7999992370605px">The point is that it doesn't need a terminal value. Infinite lists like oddsFrom3 and (repeat "foo") and (let xs = 1 : xs) are all perfectly valid Haskell values.</span></div></div><div class="HOEnZb"><div class="h5"><br><div class="gmail_quote"><div dir="ltr">On Mon, Aug 17, 2015 at 6:17 AM Doug McIlroy <<a href="mailto:doug@cs.dartmouth.edu" target="_blank">doug@cs.dartmouth.edu</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">> > oddsFrom3 :: [Integer]<br>
> > oddsFrom3 = 3 : map (+2) oddsFrom3<br>
> ><br>
> ><br>
> > Thanks for your help.<br>
><br>
> Try to expand a few steps of the recursion by hand e.g.:<br>
><br>
> 3 : (map (+2) (3 : map (+2) (3 : map (+2) ...)))<br>
><br>
><br>
> As you can see, the deeper you go more 'map (+2)' are applied to '3'.<br>
<br>
Some more ways to describe the program, which may be useful:<br>
<br>
As with any recursive function, assume you know the whole series and<br>
then confirm that by verifying the inductive step. In this case<br>
oddsFrom3 = [3,5,7,9,11,...]<br>
map (+2) oddsFrom3 = [5,7,9,11,13,...]<br>
voila<br>
oddsFrom3 = 3 : map (+2) oddsFrom3<br>
<br>
Assuming we have the whole series, we see its tail is<br>
computed from the whole by adding 2 to each element.<br>
Notice that we don't actually have to know the values in the<br>
tail in order to write the formula for the tail.<br>
<br>
Yet another way to describe the program: the "output" is taken<br>
as "input". This works because the first element of the output,<br>
namely 3, is provided in advance. Each output element can then<br>
be computed before it is needed as input.<br>
<br>
In an imperative language this would be done so:<br>
integer oddsFrom3[0:HUGE]<br>
oddsFrom3[0] := 3<br>
for i:=1 to HUGE do<br>
oddsFrom3[i] = oddsFrom3[i-1] + 2<br>
_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org" target="_blank">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
</blockquote></div>
</div></div><br>_______________________________________________<br>
Beginners mailing list<br>
<a href="mailto:Beginners@haskell.org">Beginners@haskell.org</a><br>
<a href="http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners" rel="noreferrer" target="_blank">http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners</a><br>
<br></blockquote></div><br></div></div>