シーケンス計算に必要な最小限のシーケンス「プリミティブ」とは何ですか？

Question

私はインタプリタでSchemeのようなものを書いています。 Schemeのようなインタプリタは、IEnumerableを実装するオブジェクトでうまく動作するはずです。

インタープリタは突然変異を許可していません。副作用のある関数は公開されていません。

IEnumerableは複製できないため（hereを参照）、carとcdrを使用して効率的にリストを反復処理することはできません。

"高次の"ものが効率的になるためには、インタプリタ用のC＃ビルトインとしていくつかのプリミティブを実装しなければなりませんでした。

1. フィルタ
2. マップ（フルマップだけでmapcarない）
3. foldr

しかし：

は、これまでのところ私はC＃組み込み関数として、以下の "プリミティブ" を実施しています私は恐らく、おそらくmapとfoldrの組み合わせを使って "filter"を実装できると思う。

余分なランタイムやスペースのコストをかけずにIEnumerableインスタンス上で他の機能を実装できるように、そして組み込みを導入することなく、「組み込み関数」として公開する必要がある最小限のプリミティブは何ですか？

Answer 1

System.Linq名前空間には、すべての機能が既に用意されています。

マップは= =集計（foldr =その後、集計をリバース）

を減らす/

倍を選択

1. フィルタは=

あなたはより多くのを見つけるでしょう。例えば

SelectMany =マップ+マップ+ GROUPBY =パーティション

remqと友人は、フィルタの条件で行うことができる平ら。

更新

これらは明らかにのみ、通常のスキームの定義とは異なり、1つのリストを引数に取ります。

Answer 2

foldrで定義できるので、mapは基本的にプリミティブである必要はありません。

例（Haskellでは）：

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

これは本当にmapcarmapではありませんが、フルmapはapplyが利用できないようHaskellで表現することは困難です。（スキーム中）

より完全な例：

(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))))) 

そして、あなたは、例えば、それらを定義する他の方法があるcdrcarを持っていない場合お使いの言語で閉鎖&の変数がある場合：

(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

を私は（つまり、ネストされたシーケンスを平らに）あなたがあなたの順序の計算とを目指しているものの機能はかなりわからないんだけど、連結操作あまりに非常に便利かもしれません。 Haskellのリスト内包表記がどうしてその理由を知ることができるかを見てみましょう。