[Haskell-beginners] oddsFrom3 function

[akash g]

@Rein:
Perhaps I should have been a bit more clear.  There is no way to get a
terminal value from said function.


oddsFrom3 :: [Integer]
oddsFrom3 = map (+2) oddsFrom3

Try a head for it perhaps.

oddsFrom3 = map (+2) oddsFrom3
<=> ((head  oddsFrom3) + 2) : map (+2) ((tail  oddsFrom3) + 2)
<=> ((head (map (+2) oddsFrom3) + 2) : map (+2) ((tail  oddsFrom3) + 2)

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.


Take an infinite list as an example.

x a = a :  x a

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.

Try x a = x a ++ x a

And think of the getting the head from this.  You're stuck in an infinite
loop.

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.



On Mon, Aug 17, 2015 at 10:23 PM, Rein Henrichs <rein.henrichs at gmail.com>
wrote:

> > The initial version which the OP posted doesn't have a terminal value.
>
> 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.
>
> On Mon, Aug 17, 2015 at 6:17 AM Doug McIlroy <doug at cs.dartmouth.edu>
> wrote:
>
>> > > oddsFrom3 :: [Integer]
>> > > oddsFrom3 = 3 : map (+2) oddsFrom3
>> > >
>> > >
>> > > Thanks for your help.
>> >
>> > Try to expand a few steps of the recursion by hand e.g.:
>> >
>> >    3 : (map (+2) (3 : map (+2) (3 : map (+2) ...)))
>> >
>> >
>> > As you can see, the deeper you go more 'map (+2)' are applied to '3'.
>>
>> Some more ways to describe the program, which may be useful:
>>
>> As with any recursive function, assume you know the whole series and
>> then confirm that by verifying the inductive step. In this case
>>         oddsFrom3          = [3,5,7,9,11,...]
>>         map (+2) oddsFrom3 = [5,7,9,11,13,...]
>> voila
>>         oddsFrom3 = 3 : map (+2) oddsFrom3
>>
>> Assuming we have the whole series, we see its tail is
>> computed from the whole by adding 2 to each element.
>> Notice that we don't actually have to know the values in the
>> tail in order to write the formula for the tail.
>>
>> Yet another way to describe the program: the "output"  is taken
>> as "input". This works because the first element of the output,
>> namely 3, is provided in advance. Each output element can then
>> be computed before it is needed as input.
>>
>> In an imperative language this would be done so:
>>         integer oddsFrom3[0:HUGE]
>>         oddsFrom3[0] := 3
>>         for i:=1 to HUGE do
>>                 oddsFrom3[i] = oddsFrom3[i-1] + 2
>> _______________________________________________
>> Beginners mailing list
>> Beginners at haskell.org
>> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>>
>
> _______________________________________________
> Beginners mailing list
> Beginners at haskell.org
> http://mail.haskell.org/cgi-bin/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/beginners/attachments/20150817/b3d7c3f0/attachment.html>