Re: Curry-on to infinity

From: Sebastian Hanowski <sebastian_hanowski_at_gmx.de>
Date: Mon, 21 Dec 2015 09:15:18 +0100

On Tue, Dec 15, 2015 at 10:15:09AM -0800, h7sa_at_pdx.edu wrote:
> Sebastian,
>
> This program is clever, but I like more your original one:
>
> fib | head x =?= 1
> & head (tail x) =?= 1
> & tail (tail x) =?= zipWith (+) x (tail x) = x where x free
>
> since it more clearly shows the conditions that you impose on the output. I
> changed the syntax of the equality operator, since I think that you want some
> kind of equality less strict than the standard one and different from (=:<=)
> which is intended for a different use.

Hi Sergio

how nice. I couldn't have asked for more.

And yes, I prefer the origininal formulation too because it closely resemlbles
the traditional definition of the function N -> N computing the nth fibonacci
number.
However there's some sort of 'negative' twist in here. Which of course is no
wonder, since we are dealing with infinite objects.

I immediately came up with the first program when I was contemplating on some
work by Andreas Abel. But this topic has gained some momentum in my text
editor.

For example here's some of this weekends findings: a 'slide' variation of the
fibonacci theme featuring a 'questionable' variant of Markus Schnell's stream
transducer.

        slide :: ([a] -> a) -> [a] -> [a]
        slide f as | head xs =?= f as
                    & tail xs =?= slide f (tail as) = xs where xs free

        fibstep :: [Int] -> Int
        fibstep xs = head xs + head (tail xs)

        fibs | head xs =?= 1
              & head (tail xs) =?= 1
              & tail (tail xs) =?= slide fibstep xs = xs where xs free


And here's a new way to define cycles:

Instead of writing e.g.

  -- l_1_23rc = 1 : 2 : 3 : tail l_1_23rc

for [1,2,3,2,3,....]

you can also use back pointers.

        l_1_23rc | head xs =?= 1
                  & head (tail xs) =?= 2
                  & head (tail (tail xs)) =?= 3
                  & tail (tail (tail xs)) =?= tail xs = xs where xs free

                  ,-------\
                  v /
              1 : 2 : 3 :


Cyclic data structures are essentially quotients. Which is another good
reason for not using constructors.


Best regards

Sebastian
_______________________________________________
curry mailing list
curry_at_lists.RWTH-Aachen.DE
http://MailMan.RWTH-Aachen.DE/mailman/listinfo/curry

Received on Mon Dec 21 2015 - 17:47:17 CET

This archive was generated by hypermail 2.3.0 : Mon Sep 23 2019 - 07:15:09 CEST