What's the minimal set of sequence "primitives" required for any sequence computations?

Question

I am writing a Scheme-like in interpreter. It seems natural that the Scheme-like interpreter ought to work well with any object that implements IEnumerable.

The interpreter does not allow for mutation - no functions with side effects are exposed.

Because IEnumerable is not cloneable, (see here ), I can't implement iteration over the list efficiently using car and cdr.

In order to allow any "higher order" stuff to be efficient then, I've had to implement some primitives as C# builtins for the interpreter.

So far I have implemented the following "primitives" as C# builtin functions:

1. filter
2. map (the full map, not just mapcar)
3. foldr

But I suspect, for example, that I could probably implement "filter" using a combination of map and foldr.

What is the minimal set of primitives I would need to expose as "builtins" such that I can implement any other functionality over IEnumerable instances without excess runtime or space costs, and without having to introduce mutation?

Answer 1

All the functions are already there for you in the System.Linq namespace.

1. filter = Where
2. map = Select
3. fold/reduce = Aggregate (foldr = Reverse then Aggregate)

You will find many more. Eg

SelectMany = map + map + flatten GroupBy = partition

remq and friends can be done in terms of filter.

Update

These obviously only take 1 single list argument, unlike the normal Scheme definitions.

Answer 2

You don't strictly need map to be a primitive as you can define it in terms of foldr.

Example (in Haskell):

map f = foldr (\a b->f a:b) []

This is really mapcar not map, but full map is difficult to express in Haskell as apply is not available.

More complete example (in Scheme):

(define (mapcar f l)
  (foldr (lambda (x t) (cons (f x) t)) ‛() l))

(define (heads ls) (mapcar car ls))

(define (tails ls) (mapcar cdr ls))

(define (any-null? ls) (foldr and? ﹟t (mapcar null? ls)))

(define (map f . ls)
  (if (any-null? ls)
      ‛()
      (cons (apply f (heads ls)) (apply map f (tails ls)))))

And if you don't have car and cdr there are other ways to define them, e.g. if you have closures & variables in your language:

(define (car a) (foldr (lambda (x y) x) ﹟f a))

(define (cdr a)
  (let ((prev ‛())
        (tmp #f))
    (foldr (lambda (h t) (set! tmp (cons h t)) (set! prev t) tmp)
           ‛()
           a)
    prev))

Answer 3

I'm not quite sure what functionality you are aiming for with your sequence computations, but a concat operation (i.e. flatten nested sequences) might be very useful too. Take a look at how Haskell's list comprehensions are desugared to see why.