Was ist der minimale Satz von Sequenz- "Primitiven", die für irgendwelche Sequenzberechnungen benötigt werden?

Question

Ich schreibe einen Scheme-like in Interpreter. Es scheint natürlich, dass der Scheme-like-Interpreter gut mit jedem Objekt zusammenarbeiten sollte, das IEnumerable implementiert.

Der Interpreter lässt keine Mutation zu - keine Funktionen mit Nebenwirkungen sind offengelegt.

Da IEnumerable nicht klonbar ist (siehe here), kann ich die Iteration über die Liste nicht effizient mit Auto und Cdr implementieren.

Um jede "höhere Ordnung" Zeug effizient dann zu ermöglichen, musste ich einige Primitive als C# Builtins für den Interpreter implementieren.

Bisher habe ich die folgenden "Primitiven", wie C# eingebaute Funktionen implementiert:

1. Filter
2. Karte (die Karte vergrößern, nicht nur mapcar)
3. foldr

Aber Ich vermute zum Beispiel, dass ich wahrscheinlich "Filter" mit einer Kombination aus Map und Foldr implementieren könnte.

Was ist die minimale Menge von Primitiven, die ich als "Butintins" bereitstellen müsste, damit ich andere Funktionen ohne IEnumerable-Instanzen ohne zusätzliche Laufzeit- oder Platzkosten implementieren kann, ohne eine Mutation einführen zu müssen?

Answer 1

Alle Funktionen sind bereits für Sie im System.Linq-Namespace vorhanden.

1. filter = Wo
2. map =
3. fach Auswahl/reduzieren = Aggregate (foldr = rückwärts dann Aggregate)

Sie werden viele mehr. ZB

Select = Karte + Karte + abflachen GroupBy = Partition

remq und Freunde können in Bezug auf Filter erfolgen.

aktualisiert

Diesen offensichtlich nimmt nur 1 einzige Liste Argument, im Gegensatz zu den normalen Schema-Definitionen.

Answer 2

Sie brauchen nicht unbedingt map um ein primitiv zu sein, wie Sie es in Bezug auf foldr definieren können.

Beispiel (in Haskell):

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

Das ist wirklich mapcar nicht map, aber voll map ist schwierig, in Haskell als apply auszudrücken, ist nicht verfügbar.

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

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

Und wenn Sie nicht über car und cdr gibt es andere Möglichkeiten, sie zu definieren, z.B. wenn Sie Schließungen & Variablen in Ihrer Sprache haben:

(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

Ich bin nicht ganz sicher, welche Funktionen Sie mit Ihrer Sequenz Berechnungen zielen, sondern eine concat Operation (d verschachtelte Sequenzen abflachen) könnte sehr nützlich sein. Werfen Sie einen Blick darauf, wie Haskells Listenerläuterungen entziffert werden, um zu sehen, warum.