[Haskell-beginners] oddsFrom3 function

[Rein Henrichs]

It isn't an inductive structure. It's a *coinductive* structure. And yes,
coinductive structures are useful in plenty of scenarios.

On Mon, Aug 17, 2015 at 10:30 AM akash g <akaberto at gmail.com> wrote:

> Oh, it is a valid value (I think I implied this by saying they'll compile
> and you can even evaluate).  Just not useful in any given scenario (an
> inductive structure where you don't have terminals).
>
>
> On Mon, Aug 17, 2015 at 10:57 PM, akash g <akaberto at gmail.com> wrote:
>
>> @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
>>>
>>>
>>
> _______________________________________________
> 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/32d399d4/attachment.html>