Curry-on to infinity

From: Sebastian Hanowski <sebastian_hanowski_at_gmx.de>
Date: Fri, 4 Dec 2015 09:04:02 +0100


Hi all,


Haskell sometimes get's critisized for collapsing the notion of finite
and infinite data because the latter should be opaque like functions
or that it requires you to mention lazy evaluation when explaining
non-terminating recursive definitions.

Applying the same critique to Curry seems somehow unfair since it
already contains a remedy!

Instead of writing for example the fibonaci sequence in terms of
constructors and self reference

-- fib = 1 : 1 : zipWith (+) fib (tail fib)

Curry alternativly let's you define it this way

fib | head x =:<= 1
    & head (tail x) =:<= 1
    & tail (tail x) =:<= zipWith (+) x (tail x) = x where x free

Since we know now that it's possible to define the program without
having to mention constructors, the next step would be to completely
hide the concrete representation in a module with only the selection
functions being exported.

module Stream(Stream,sHead,sTail) where ...

However since the fibonacci sequence is my running example please allow
that we assume this as already working, induct on this and proceed
directly to the next next step by combining both previous results ;)

If we seal a definition of an infinite data structure in a module
aliasing it's constructor with a defined function e. g. by saving the
following to a file

module Stream(Stream,(>:)) where

data Stream a = SCons a (Stream a)

infix r 5
(>:) :: a -> Stream a -> Stream a
a >: as = SCons a as

we not only do justice to progamming by just specifying an abstract
implementation

import Stream

fib :: Stream a
fib | sHead x =:<= 1
    & sHead (sTail x) =:<= 1
    & sTail (sTail x) =:<= sZipWith (+) x (sTail x) = x where x free

but also do we get back our familiar mode of programming with pattern
matching and constructor calls.

sHead :: Stream a -> a
sHead (a>:_) = a

sTail :: Stream a -> Stream a
sTail (_>:as) = as

sZipWith :: (a -> b -> c) -> Stream a -> Stream b -> Stream c
sZipWith f (a>:as) (b>:bs) = f a b >: sZipWith f as bs

-- just a utility for use on the console
sTake :: Int -> Stream a -> [a]
sTake n (a>:as) | n == 0 = [] | otherwise = a : sTake (n-1) as

Have your choice!
Please note that the latter also is still independent of the concrete
implementation of Stream.
You could silently switch the imported module back to say

type Stream a = [a]
(>:) = (:)

and my program wouldn't (have to) recognise it.

If you find this as interesting as I do, can you write other sequences in
either way? Primes? Hamming numbers?

Your PAKCS source code distribution contains a file examples/inflists.curry if
you want to cut short on the maths part of that tasks. (As I did).

So my point is just that free variables seem to be a nice tool for handling
abstract data (what infinite data should be, as some argue) and that function
calls on the left can be used to restore a convenient interface to it.
They can be used to visualize data our program never gets to see.


Have a nice weekend

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

Received on Mo Dez 07 2015 - 16:49:30 CET

This archive was generated by hypermail 2.3.0 : Do Feb 01 2024 - 07:15:12 CET