From: ····@pobox.com
Subject: DB:for-each and "map -> unfold -> lens -> Y" list generators' hierarchy
Date:
Message-ID: <72npe3$552$1@nnrp1.dejanews.com>
At ICFP'98, Jonathan Sobel, on behalf of himself and Daniel
P. Friedman uttered a battle cry "Use ANA!". It was at the end of his
talk "Recycling continuations". This talk had proved that anamorphisms
can be very efficiently compiled and executed without leaving no or
little garbage. The previous post -- Platform-independent higher-order
distributed SQL database interface -- introduced a function
DB:for-each. This iterator acts like a 'map' on the results of the
query - but not quite. Unlike map, DB:for-each may skip elements, and
may terminate prematurely. This article is to show that 'map' and
'unfold' are not powerful enough to express DB:for-each; DB:for-each
is an anamorphism and thus _requires_ a more capable list generator.
List generators make lists, given a user function and a "seed". That's
where the similarity ends: list generators differ in expressiveness
and power, and can be arranged in a pecking order
map -> unfold -> anamorphism -> Y
DB:for-each makes a good example showing that the list generators are
not created equal.
The problem is to implement DB:for-each along the following lines
(define (DB:for-each PROC SQL-strings)
(<COMB> <F> result-set))
where the result-set is an abstract data type (accessed via a
next-row! method), <COMB> is one of the list constructors or a trivial
glue to it, and <F> is a *simple* function. We specifically forbid <F>
any recursion or iteration; the execution flow graph of <F> must not
have any directed cycles. All iterations must be performed exclusively
by a list generator - if it can.
Obviously, 'map' is not up to this task. It requires the seed be a
list; 'map' walks this list itself, and constructs the result list in
its own private way; the user function can access neither list, only
the current element. The user function can't tell 'map' to stop after
a specific element, nor can it yield a "void". On the other end of the
spectrum, the Y combinator doesn't care what the seed is, how the
result list is constructed or when to terminate. It only iterates,
everything else is the responsibility of a user function. As Y is
capable of anything and is the least convenient for the user, it won't
be considered here.
The unfold list constructor:
(unfold p f g seed) = (if (p seed) '()
(cons (f seed) (unfold p f g (g seed))))
treats the seed as an abstract data type: it is only accessed via
user-supplied functions. It's the user -- function P -- who will
decide when to stop iterating. Alas, once (f seed) is evaluated, its
result invariably becomes a part of the list being unfolded. Thus only
anamorphism is general enough to implement DB:for-each.
But first, about Sobel's paper. Unfortunately, his definition of
list-anamorophism needs extension. He defined a function (remove x L)
that removes all instances of x from a list L as an anamorphism:
<BLOCKQUOTE CITE="Proc. ICFP'98, p. 259">
(define List-map (lambda (f l)
(List-case l
((Empty-List) (Empty-List))
((Pair h t) (Pair h (f t))))))
(define List-ana (lambda (psi)
(letrec ((f (lambda (l) (List-map f (psi l)))))
f)))
(define remove (lambda (x l))
((List-ana (lambda (l)
(List-case l
((Empty-List) l)
((Pair h t) (if (equal? h x) t l)))))
l)))
</BLOCKQUOTE>
Unfortunately, this 'remove' doesn't quite cut it: consider applying
it to a list '(3 3). It would return '(3) while the expected result is
'()
I have modified Sobel's anamorphism as follows; I also re-wrote it in
a more conventional Scheme notation:
; The second argument of the following function maybe-map-cdr is
; datatype L 'a = Nil | Cons (Maybe 'a) L
; where
; datatype Maybe 'a = Nothing | Some 'a
; May ML programmers forgive me...
(define (Maybe . x) x)
(define Nothing? null?)
(define Something car)
(define (maybe-map-cdr f L)
(cond ((null? L) '())
((Nothing? (car L)) (f (cdr L)))
(else (cons (Something (car L)) (f (cdr L))))))
; A lens: the ana generator (quoted almost literally from the Sobel's
; paper)
; Given psi, it returns an anamorhism over it, which satisfies
; an equation
; (equal?
; (maybe-map-cdr (list-ana psi) (psi L))
; ((list-ana psi) L))
; for each L within psi's domain.
(define (list-ana psi)
(define (ana-psi L) (maybe-map-cdr ana-psi (psi L)))
ana-psi)
(define (remove x L) ((list-ana
(lambda (l)
(cond ((null? l) l)
((equal? x (car l)) (cons (Maybe) (cdr l)))
(else (cons (Maybe (car l)) (cdr l)))))) L))
(remove 3 '(1 2 3 4 3 5)) => (1 2 4 5)
(remove 3 '(1 2 3 3 4 5)) => (1 2 4 5)
(remove 3 '(3 3)) => ()
(remove '(3) '(3 4 5 (3) () 6)) => (3 4 5 () 6)
; Now DB:for-each as a list-anamorphism
; Incidentally, this serves as an 'operational semantics'
; definition for DB:for-each
(define (DB:for-each PROC . sql-strings)
((list-ana
(lambda (result-set)
(let* ((curr-row (next-row! result-set))
(PROC-result (and curr-row (apply PROC curr-row))))
(cond
((not PROC-result) '())
((null? PROC-result) (cons (Maybe) result-set))
(else (cons (Maybe PROC-result) result-set))))))
(apply SQL-executor sql-strings)))
; A SQL-executor takes a list of strings that together define a
; valid SQL statement, executes this statement, and returns
; a result-set. A result-set is an abstract data type.
; The only use of a result-type object is to give it to
; next-row! The latter will return the current row (as a list
; of its fields' values) or #f. The next-row! will also modify
; the result-set to "point" to the next row of the query result table.
; For illustration, result-set is defined here as a simple pair
; with an obvious meaning curr-value . max-value
(define (SQL-executor . dummy) (cons 0 10))
(define (next-row! result-set)
(let ((curr-val (car result-set)))
(and (< curr-val (cdr result-set))
(begin (set-car! result-set (+ 1 curr-val))
(list curr-val)))))
(DB:for-each (lambda (val) (if (odd? val) val '()))
"SELECT dummy") => (1 3 5 7 9)
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Steve Gonedes
Subject: Re: DB:for-each and "map -> unfold -> lens -> Y" list generators' hierarchy
Date:
Message-ID: <m23e7kp9la.fsf@KludgeUnix.com>
····@pobox.com writes:
<
< At ICFP'98, Jonathan Sobel, on behalf of himself and Daniel
< P. Friedman uttered a battle cry "Use ANA!". It was at the end of his
< talk "Recycling continuations". This talk had proved that anamorphisms
< can be very efficiently compiled and executed without leaving no or
< little garbage. The previous post -- Platform-independent higher-order
< distributed SQL database interface -- introduced a function
< DB:for-each. This iterator acts like a 'map' on the results of the
< query - but not quite. Unlike map, DB:for-each may skip elements, and
< may terminate prematurely. This article is to show that 'map' and
< 'unfold' are not powerful enough to express DB:for-each; DB:for-each
< is an anamorphism and thus _requires_ a more capable list generator.
<
< List generators make lists, given a user function and a "seed". That's
< where the similarity ends: list generators differ in expressiveness
< and power, and can be arranged in a pecking order
< map -> unfold -> anamorphism -> Y
< DB:for-each makes a good example showing that the list generators are
< not created equal.
<
< The problem is to implement DB:for-each along the following lines
< (define (DB:for-each PROC SQL-strings)
< (<COMB> <F> result-set))
< where the result-set is an abstract data type (accessed via a
< next-row! method), <COMB> is one of the list constructors or a trivial
< glue to it, and <F> is a *simple* function. We specifically forbid <F>
< any recursion or iteration; the execution flow graph of <F> must not
< have any directed cycles. All iterations must be performed exclusively
< by a list generator - if it can.
<
< Obviously, 'map' is not up to this task. It requires the seed be a
< list; 'map' walks this list itself, and constructs the result list in
< its own private way; the user function can access neither list, only
< the current element. The user function can't tell 'map' to stop after
< a specific element, nor can it yield a "void". On the other end of the
< spectrum, the Y combinator doesn't care what the seed is, how the
< result list is constructed or when to terminate. It only iterates,
< everything else is the responsibility of a user function. As Y is
< capable of anything and is the least convenient for the user, it won't
< be considered here.
<
< The unfold list constructor:
< (unfold p f g seed) = (if (p seed) '()
< (cons (f seed) (unfold p f g (g seed))))
< treats the seed as an abstract data type: it is only accessed via
< user-supplied functions. It's the user -- function P -- who will
< decide when to stop iterating. Alas, once (f seed) is evaluated, its
< result invariably becomes a part of the list being unfolded. Thus only
< anamorphism is general enough to implement DB:for-each.
<
< But first, about Sobel's paper. Unfortunately, his definition of
< list-anamorophism needs extension. He defined a function (remove x L)
< that removes all instances of x from a list L as an anamorphism:
< <BLOCKQUOTE CITE="Proc. ICFP'98, p. 259">
< (define List-map (lambda (f l)
< (List-case l
< ((Empty-List) (Empty-List))
< ((Pair h t) (Pair h (f t))))))
< (define List-ana (lambda (psi)
< (letrec ((f (lambda (l) (List-map f (psi l)))))
< f)))
< (define remove (lambda (x l))
< ((List-ana (lambda (l)
< (List-case l
< ((Empty-List) l)
< ((Pair h t) (if (equal? h x) t l)))))
< l)))
< </BLOCKQUOTE>
List-case is undefined? What is an anamorphism?
< Unfortunately, this 'remove' doesn't quite cut it: consider applying
< it to a list '(3 3). It would return '(3) while the expected result is
< '()
<
< I have modified Sobel's anamorphism as follows; I also re-wrote it in
< a more conventional Scheme notation:
<
< ; The second argument of the following function maybe-map-cdr is
< ; datatype L 'a = Nil | Cons (Maybe 'a) L
< ; where
< ; datatype Maybe 'a = Nothing | Some 'a
< ; May ML programmers forgive me...
<
< (define (Maybe . x) x)
< (define Nothing? null?)
< (define Something car)
Why not use `rest' or `cdr' instead of the `.'? I can understand why
someone wouldn't like cdr, but what's wrong with rest? Just curious.
< (define (maybe-map-cdr f L)
< (cond ((null? L) '())
< ((Nothing? (car L)) (f (cdr L)))
< (else (cons (Something (car L)) (f (cdr L))))))
<
< ; A lens: the ana generator (quoted almost literally from the Sobel's
< ; paper)
< ; Given psi, it returns an anamorhism over it, which satisfies
< ; an equation
< ; (equal?
< ; (maybe-map-cdr (list-ana psi) (psi L))
< ; ((list-ana psi) L))
< ; for each L within psi's domain.
<
< (define (list-ana psi)
< (define (ana-psi L) (maybe-map-cdr ana-psi (psi L)))
< ana-psi)
<
< (define (remove x L) ((list-ana
< (lambda (l)
< (cond ((null? l) l)
< ((equal? x (car l)) (cons (Maybe) (cdr l)))
< (else (cons (Maybe (car l)) (cdr l)))))) L))
<
< (remove 3 '(1 2 3 4 3 5)) => (1 2 4 5)
< (remove 3 '(1 2 3 3 4 5)) => (1 2 4 5)
< (remove 3 '(3 3)) => ()
< (remove '(3) '(3 4 5 (3) () 6)) => (3 4 5 () 6)
Maybe I am missing something, but why not just use a local function
and push the items you want into a new list? You'll still have to
iterate through the entire list of course, and mostlikely it's not all
that efficient. Maybe you could write a macro that binds the good
value to some known name and funcalls some user code - this is nice if
you just want to do something with some items in a list and don't need
a list returned.
(defun list-map (procedure list-of-stuff)
(do ((list list-of-stuff (cdr list)))
((null list))
(funcall procedure (car list))))
(defun remove-number (number list-of-numbers)
(let ((newlist ()))
(list-map #'(lambda (num)
(unless (= num number)
(push num newlist)))
list-of-numbers)
newlist))
(remove-number 3 '(1 2 3 3 4 3 1 9 2837))
=> (2837 9 1 4 2 1)
It seems like you want `find-if', `push-if', or maybe just `block'.
I'm probably just missing something.
Here's what I meant by a binding-function.
(defun with-items-of-list (test-fn action-fn list)
(dolist (item list)
(when (funcall test-fn item)
(funcall action-fn item))))
(with-items-of-list #'numberp #'print '("one" 1 "two" 2))
You can still do,
(let ((newlist ()))
(with-items-of-list
#'numberp #'(lambda (x) (push x newlist))
'("one" 1 "two" 2))
newlist)
=> (2 1).
Sorry if all of this is obvious - was just curious...
From: Gareth McCaughan
Subject: Re: DB:for-each and "map -> unfold -> lens -> Y" list generators' hierarchy
Date:
Message-ID: <864srywog9.fsf@g.pet.cam.ac.uk>
Steve Gonedes wrote:
>< (define (Maybe . x) x)
>< (define Nothing? null?)
>< (define Something car)
>
> Why not use `rest' or `cdr' instead of the `.'? I can understand why
> someone wouldn't like cdr, but what's wrong with rest? Just curious.
(define (Maybe . x) x) in Scheme equals
(defun maybe (&rest x) x) in Common Lisp.
It's not the same as using "rest" or "car". It is, on the other hand,
the same thing as "list".
> It seems like you want `find-if', `push-if', or maybe just `block'.
> I'm probably just missing something.
The fact that he's writing in Scheme, which doesn't have these?
I presume the "anamorphism" stuff is also meant to be useful in
a much more general setting, but the article doesn't make it clear
to me how.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
·····@dpmms.cam.ac.uk Cambridge University, England.
From: Steve Gonedes
Subject: Re: DB:for-each and "map -> unfold -> lens -> Y" list generators' hierarchy
Date:
Message-ID: <m2k90udrsa.fsf@KludgeUnix.com>
Gareth McCaughan <·····@dpmms.cam.ac.uk> writes:
< Steve Gonedes wrote:
<
< >< (define (Maybe . x) x)
< >< (define Nothing? null?)
< >< (define Something car)
< >
< > Why not use `rest' or `cdr' instead of the `.'? I can understand why
< > someone wouldn't like cdr, but what's wrong with rest? Just curious.
<
< (define (Maybe . x) x) in Scheme equals
< (defun maybe (&rest x) x) in Common Lisp.
< It's not the same as using "rest" or "car". It is, on the other hand,
< the same thing as "list".
I was thinking the `.' would pull apart the list, like
(destructuring-bind (x . y)
'(1 (2 3))
y)
=> ((2 3)).
< > It seems like you want `find-if', `push-if', or maybe just `block'.
< > I'm probably just missing something.
<
< The fact that he's writing in Scheme, which doesn't have these?
That's why I mentioned it, they are useful. I guess block can't be
written easily, but find-if and such could be done with a fair amount
of ease.
> I presume the "anamorphism" stuff is also meant to be useful in a
> much more general setting, but the article doesn't make it clear to
> me how.
I admit. I plead the second chance. Let me start again with the
function (remove x L), which removes all occurrences of x from a list
L while _preserving_ the list's order. As Steve Gonedes rightfully
noted, one can implement 'remove' using a simpler iterator, being
applied to a non-recursive non-iterating user-function:
(define (remove x L)
(reverse
(let ((res '()))
(for-each (lambda (el) (or (equal? x el) (push! el res))) L)
res)))
where push! is a suitably defined macro
(remove 3 '(1 2 3 3 4 3 1 9 2837)) ==> (1 2 4 1 9 2837)
You can even use map:
(define (Maybe . x) x) ; from the previous article
(define Nothing? null?)
(define Something car)
(define (another-remove x L)
(flatten
(map
(lambda (el) (if (equal? x el) (Maybe) (Maybe el)))
L)))
(another-remove 3 '(1 2 3 3 4 3 1 9 2837)) ==> (1 2 4 1 9 2837)
What's unsatisfactory with both these solution is that I have to use
another iteration (performed by 'reverse' or 'flatten') after the
primary filtering iteration. In the case of map, this secondary
post-processing (flatten) is actually more complex than the primary
iteration itself.
I thought up the last example on Tue evening while falling asleep. On
Wed afternoon, I saw a follow-up by Jeremy Gibbons and his
implementation of 'filter', in Haskell. I was startled to realize how
his code is similar to the one above! Uncanny things happen in the
twilight zone indeed. Here's Jeremy Gibbons' code, for comparison:
filter p = squeeze . cancel p
where
cancel :: (a->Bool) -> [a] -> [ Maybe a ]
cancel p = map ( \ x -> if p x then Nothing else Just x )
squeeze :: [ Maybe a ] -> [a]
squeeze [] = []
squeeze (Nothing : x) = squeeze x
squeeze (Just a : x) = a : squeeze x
I must get back to the point, sorry.
> It seems like you want `find-if', `push-if', or maybe just `block'.
> I'm probably just missing something.
One can certainly use find-if, or better yet, filter to implement
remove. Although R5RS does not specify 'filter', Olin Shiver's
excellent RFI does. Besides, it's trivial to implement, for example,
(define (filter pred? L)
(cond
((null? L) L)
((pred? (car L)) (cons (car L) (filter pred? (cdr L))))
(else (filter pred? (cdr L)))))
This obviously a recursive function. One can implement it with a named
let, letrec etc constructions, which are actually all the same (and
probably could be mechanically transformed into one another). There is
the Y combinator lurking in here: it is the ultimate iterator, and
through it (or its incarnation like define, letrec, named loop) all
things possible. But what if we don't have the Y combinator?
Furthermore, what if we are not permitted an unbridled recursion?
To show that there may be a virtue in moderation, let me invoke
goto. It is the ultimate control structure which can implement all the
others, and then some. Yet there is a strong opinion that goto is just
too powerful for its own good. Only compilers should be able to use
branching and jumping, people are not to be trusted with such sharp
objects. We should be content with restricted forms of goto like
'break', 'continue', 'throw', 'raise', and various forms of loop
constructs.
As another (side)example of moderation, consider Linear Algebra. The
word 'matrix' invariably brings to mind an ability to get to the
i,j-th element. But what if one can't access a matrix at an arbitrary
location? What can we do with only consecutive access via various
kinds of streams? Surprisingly a lot, if my LinALg package is of any
indication. You can compute determinant, a Gauss-Jordan matrix inverse
with full pivoting, matrix bidiagonalization with Householder
transformations, and even to a large extent Singular Value
Decomposition (SVD). There is a noticeable practical value in this
particular exercise: the algorithms and the code become
"stream"-lined, a serial access is cheaper than the arbitrary one,
streams lend themselves to vector and similar SIMD processing, to
modern memory architectures, etc. I can talk long and boring about
this, although probably on a different newsgroup: LinAlg is written in
C++. Sorry. Although if you look at the code and see LazyMatrices
strewn around, of_every() and to_every() iterators, 'apply' methods
and a couple of Lambdas - you may doubt the language as well.
IMHO, a similar argument of too much power can be made for the Y
combinator. It can't be typed, for one thing. Allowing uncontrolled
recursion lets one define functions like,
(define (fact f n) (if (zero? n) 1 (* n (f f (- n 1)))))
(fact fact 5) => 120
which will choke any static type checker.
Thus I was wondering: what if the only iterations/recursions possible
are the ones performed by iterator/generator primitives. What could
they be, how expressive and powerful can they be, and how comfortable
we would be about programming with them.
We already have a few iterators: map, unfold, anamorhism (which Sobel
calls a generalized unfold, referring to Erik Meijer et. el's paper
about bananas, barbed wire and functional programming). These
iterating primitives are not created equal. For example, unlike map,
unfold treats its seed as an abstract data type. Thus one can unfold a
list out of something else. Yet unfold can't implement filter without
help of other iterators, as Jeremy Gibbons showed (as it is impossible
to get a potentially divergent function out of an always convergent
one using only 'simple' combinators - sequencing and branching). That
was the subject of the previous article. It showed that a lens
constructor that makes an anamorphism lends an additional power to
unfold. DB:for-each seemed to be a particularly good example as it
requires a seed as an abstract data type, skipping, and premature
termination. BTW, unlike the general Y combinator, list-ana as defined
in the previous article has a finite and simple static type. Thus a
SoftScheme would be happy.
Unfortunately, I can read news only through DejaNews, which apparently
knows more about sorting by date than it wants to share with us.
Just a quick remark to Steve Gonedes' question:
> I was thinking the `.' would pull apart the list, like
> (destructuring-bind (x . y)
> '(1 (2 3))
> y) => ((2 3))
You are right, '.' can do that too:
(apply (lambda (x . y) y) '(1 (2 3))) => ((2 3))
-----------== Posted via Deja News, The Discussion Network ==----------
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
From: Jeremy Gibbons
Subject: Re: DB:for-each and "map -> unfold -> lens -> Y" list generators' hierarchy
Date:
Message-ID: <72un7u$bq2$1@news.ox.ac.uk>
In article <············@nnrp1.dejanews.com>, <····@pobox.com> wrote:
>At ICFP'98, Jonathan Sobel, on behalf of himself and Daniel
>P. Friedman uttered a battle cry "Use ANA!". It was at the end of his
>talk "Recycling continuations". This talk had proved that anamorphisms
>can be very efficiently compiled and executed without leaving no or
>little garbage. The previous post -- Platform-independent higher-order
>distributed SQL database interface -- introduced a function
>DB:for-each. This iterator acts like a 'map' on the results of the
>query - but not quite. Unlike map, DB:for-each may skip elements, and
>may terminate prematurely. This article is to show that 'map' and
>'unfold' are not powerful enough to express DB:for-each; DB:for-each
>is an anamorphism and thus _requires_ a more capable list generator.
I'm not sure how you use the terms, but to me "anamorphism" and "unfold"
are synonyms.
The fact that your DB:for-each is not an unfold is easily seen: an unfold
is necessarily "productive", whereas DB:for-each is not productive.
Say that function f is "anti-strict" if
x /= _|_ => f x /= _|_
that is, x is non-bottom implies f x is non-bottom. The following
definition of unfold (in Haskell, I'm afraid) is anti-strict, provided that
p is anti-strict:
unfold :: (b->Bool) -> (b->a) -> (b->b) -> b -> [a]
unfold p f g x
= if p x then [] else f x : unfold p f g (g x)
(In fact, one can state a stronger result: if p is anti-strict, then unfold p
f g generates the complete spine of a list; the only bottoms that might
appear are elements of the generated list, not cons cells.)
On the other hand, a function like filter p is not anti-strict even for
anti-strict p:
filter even ones where ones = 1 : ones
is bottom, despite the fact that the argument ones is completely defined.
Therefore filter p cannot be written as an unfold. The best one can do is
write
filter p = squeeze . cancel p
where
cancel :: (a->Bool) -> [a] -> [ Maybe a ]
cancel p = map ( \ x -> if p x then Nothing else Just x )
squeeze :: [ Maybe a ] -> [a]
squeeze [] = []
squeeze (Nothing : x) = squeeze x
squeeze (Just a : x) = a : squeeze x
Here cancel p is productive, but squeeze is not. (This example was shown to
me by Graham Hutton.)
Nothing can be done about filter; it cannot be written using coinduction as
the only means of recursion, as far as I know. However, Varmo Vene and
Tarmo Uustalu have proposed (in 9th NWPT, see
http://www.it.kth.se/~tarmo/papers/nwpt97.ps.gz) a notion of co-recursion
which they call "apomorphisms". An apomorphism is like an anamorphism, but
it may "jump straight to the answer" instead of "generating the answer item
by item". Their canonical example is the function insert, which inserts a
value into a sorted list.
insert :: Ord a => (a,[a]) -> [a]
insert (a,[]) = [a]
insert (a,b:x)
| a <= b = a : b : x
| otherwise = b : insert (a,x)
This can be written as an unfold:
insert (a,x) = unfold p f g (Just a, x) where
p (Nothing, []) = True
p _ = False
f (Just a, []) = a
f (Just a, b:x)
| a <= b = a
| otherwise = b
f (Nothing, b:x) = b
g (Just a, []) = (Nothing, [])
g (Just a, b:x)
| a <= b = (Nothing, b:x)
| otherwise = (Just a, x)
g (Nothing, b:x) = (Nothing, x)
but this algorithm generates the elements of the result one by one,
even "after" inserting the new element. Vene and Uustalu define
list apomorphisms essentially as follows:
apo :: (b->Bool) -> (b->a) -> (b->b) -> (b->[a]) -> b -> [a]
apo p f g h x
= if p x then h x else f x : apo p f g h (g x)
The difference with unfolds is the extra argument h; when p holds of the
argument x, the result is h x instead of just [], so
unfold p f g = apo p f g (const [])
Now
insert = apo p f g h where
p (a,x) = null x || a <= head x
f (a,x) = head x
g (a,x) = (a, tail x)
h (a,x) = a:x
Thus, apo provides some extra expressive power between unfolds and general
recursion. (Of course, the above is just about lists, but one can write a
single polytypic definition of apomorphisms for all datatypes.)
Jeremy
--
Jeremy Gibbons <jgibbons at brookes dot ac dot uk>
School of Computing and Mathematical Sciences, tel +44 1865 483660
Oxford Brookes University, Headington Campus, fax +44 1865 483666
Oxford OX3 0BP, UK. http://www.brookes.ac.uk/~p0071749/home.html
Curious! I just stuck UNFOLD into the list library I am proposing as an SRFI
for the Scheme community, and the exact same issue bugged me, so I added
exactly the "apomorphism" you described, calling it unfold/tail -- without
knowing of Vene & Uustalu. (My SRFI proposals are at
ftp://ftp.ai.mit.edu/pub/shivers/srfi
if you want to see the lib.)
(define (unfold/tail p f g e seed)
(let recur ((seed seed))
(if (p seed) (e seed)
(cons (f seed) (recur (g seed))))))
You need it to do some simple things:
;;; Copy a possibly non-proper list:
(unfold/tail (lambda (x) (not (pair? x))) car cdr values lis)
;;; Append HEAD onto TAIL:
(unfold/tail null? car cdr (lambda (x) tail) head)
Apomorphism. Huh. Kids today. When I was young, we were damn glad just to
get an occasional isomorphism on weekends.
-Olin
Olin Shivers <·······@lambda.ai.mit.edu> writes:
> Apomorphism. Huh. Kids today. When I was young, we were damn glad just to
> get an occasional isomorphism on weekends.
You had isomorphisms? We used to dream of having isomorphisms! Why,
when I was young we only had surjective mappings....
~jrm
In comp.lang.functional ···@rebol.com wrote:
: Olin Shivers <·······@lambda.ai.mit.edu> writes:
: > Apomorphism. Huh. Kids today. When I was young, we were damn glad just to
: > get an occasional isomorphism on weekends.
: You had isomorphisms? We used to dream of having isomorphisms! Why,
: when I was young we only had surjective mappings....
Surjective mappings! We were allowed an injection on Christmas. Other
than that it was all hand-me-downs!
--
Patrick Logan (H) ·············@teleport.com
(W) ···············@gemstone.com
http://www.gemstone.com
Patrick Logan wrote in message <······················@news.teleport.com>...
>In comp.lang.functional ···@rebol.com wrote:
>: Olin Shivers <·······@lambda.ai.mit.edu> writes:
>
>: > Apomorphism. Huh. Kids today. When I was young, we were damn glad just
to
>: > get an occasional isomorphism on weekends.
>
>: You had isomorphisms? We used to dream of having isomorphisms! Why,
>: when I was young we only had surjective mappings....
>
>Surjective mappings! We were allowed an injection on Christmas. Other
>than that it was all hand-me-downs!
Injections? You got *injections*?!? Man, we would've killed for that. We
had to go out and catch frogs and lick them ourselves!
<blink>
Oh, isn't that what we were talking about? <blush> Uh, never mind...
:-)
--
Bob Jarvis
Mail address hacked to foil spammers!
Remove "ob" from address to reply
Olin Shivers wrote:
> Apomorphism. Huh. Kids today. When I was young, we were damn glad just to
> get an occasional isomorphism on weekends.
Now they have Isomighty Apomorphin Power LaGrangers. Kids.
That reminds me, it's time to viciously flog my inner child.
Regards, [Ag] Andy Gaynor ······@mail.webspan.net