[mercury-users] map and filter

[Lee Naish]

>Hi, quick question for those in the mood for quick answers.
>
>Is there a conceivable container to which higher order operations such as
>map and filter and *not* applicable? Replace "container" with "collection"
>if it suits your purposes.

If the collection is a "shapely" data type, basically its a container
for N items and does not dependent all on what the items are (parametric
polymorphism basically; examples are lists, trees and arrays;
non-examples are ordered lists and trees and hash tables) then map
definitely makes sense but filter is not well defined (there are
typically many trees which could result from deleting some elements from
a tree with N nodes and its not easy to define a canonical one).
You can also define map2, map3, etc, same_shape and member.

If you define some ordering on the N items (eg preorder left to right
traversal for trees) then you can also define foldr, foldl and list_from
(an instance of foldl).

I have implemented a system which generates Prolog code for these
predicates from algebraic type definitions (actually its more general
than that).  See http://www.cs.mu.oz.au/~lee/papers/hose/ and check out
the work on shape/polytypism which has come out of functional programming.

There are other shapely operations also, such as transposing a
container of containers (I haven't implemented this one, though I now
know how to).

I once suggested incorporating these ideas into Mercury...

	lee
--------------------------------------------------------------------------
mercury-users mailing list
post:  mercury-users at cs.mu.oz.au
administrative address: owner-mercury-users at cs.mu.oz.au
unsubscribe: Address: mercury-users-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-users-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------