Каков минимальный набор «примитивов» последовательности, необходимый для любых вычислений последовательности?

Question

Я пишу схему в интерпретаторе. Кажется естественным, что интерпретатор, подобный Схеме, должен хорошо работать с любым объектом, который реализует IEnumerable.

Интерпретатор не допускает мутации - функции с побочными эффектами не отображаются.

Поскольку IEnumerable не является клонированным, (см. here), я не могу эффективно реализовать итерацию по списку с помощью автомобиля и cdr.

Для того, чтобы любой материал более высокого порядка был эффективным, мне пришлось реализовать некоторые примитивы как встроенные C# для интерпретатора.

До сих пор я реализовал следующие "примитивов", как C# встроенных функций:

1. фильтра
2. карта (полная карта, а не только MAPCAR)
3. foldr

Но Я подозреваю, например, что я мог бы реализовать «фильтр», используя комбинацию карты и foldr.

Каков минимальный набор примитивов, которые мне нужно будет выставлять как «встроенные», чтобы я мог реализовать любую другую функциональность над экземплярами IEnumerable без лишних затрат времени выполнения или пространства и не вводить мутацию?

Answer 1

Все функции уже существуют для вас в пространстве имен System.Linq.

1. фильтр = Где
2. карта = Выбрать
3. раз/уменьшить = совокупный (foldr = Reverse затем Aggregate)

Вы найдете много больше. Например

SelectMany = Карта + карта + расплющить GroupBy = раздел

remq и друзья могут быть сделаны через фильтр.

Update

Это, очевидно, только берут 1 единый аргумент-список, в отличие от обычных определений Scheme.

Answer 2

Вам не нужно обязательно map быть примитивным, как вы можете определить его в терминах foldr.

Пример (в Haskell):

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

Это действительно mapcar не map, но полный map трудно выразить в Haskell, как apply не доступен.

Более полный пример (на схеме):

(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 or? ﹟f (mapcar null? ls))) 

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

И если у вас нет car и cdr есть и другие способы определения их, например, если у вас есть CLOSURES & переменных на вашем языке:

(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

Я не совсем уверен, что функциональность вы стремитесь с вычислениями последовательности, но операция CONCAT (т.е. расплющить вложенные последовательности) может быть очень полезно тоже. Взгляните на то, как разоблачение списков Haskell нежелательно, чтобы понять, почему.