폴드 및 축소가 근본적인 이유 인 이유는 무엇입니까? 물론 모든 것이 단점과 자동차 측면에서 정의되어 있습니까?

Question

우리는 reduce/foldl1을 함수 by which we can define other higher order functions such as map, filter and reverse으로 사용할 수 있음을 알 수 있습니다.

(defn mapl [f coll] 
    (reduce (fn [r x] (conj r (f x))) 
      [] coll)) 

(defn filterl [pred coll] 
    (reduce (fn [r x] (if (pred x) (conj r x) r)) 
      [] coll)) 

(defn mapcatl [f coll] 
    (reduce (fn [r x] (reduce conj r (f x))) 
      [] coll)) 

우리는 또한 foldr의 관점에서이를 수행 할 수있는 것으로 보입니다. 여기에 map 및 filter은 012:의 17:25로 표시됩니다. fold와 왜

이

(defn foldr [f z xs] 
    (if (null? xs) 
     z 
     (f (first xs) (foldr f z (rest xs))))) 

(defn foldl [f z xs] 
    (if (null? xs) 
     z 
     (foldl f (f z (first xs)) (rest xs)))) 

(defn map [f lst] 
    (if (null? lst) 
     '() 
     (cons (f (first lst)) (map f (rest lst))))) 

내 질문이 입니다 :

(defn mapr [f coll] 
    (foldr (fn [x r] (cons (f x) r)) 
     () coll)) 

(defn filterr [pred coll] 
    (foldr (fn [x r] (if (pred x) (cons x r) r)) 
     () coll)) 

이제 우리는 first, rest 및 cons (car, cdr 및 cons)의 측면에서 map, foldl (reduce)와 foldr 정의 할 수 있습니다 reduce은 기본으로 간주됩니다. 확실히 모든 것이 cons, cdr 및 car? 잘못된 레벨의 것들이 보이지 않습니까?

Answer 1

Rich Hickey가 정확하게 그의 것이라고 말한 것으로 생각했습니다 talk about transducers.

그는 변형의 기본 개념으로 folds을 봅니다. 그것은 그것이 작동하고있는 구조와 그 구조에서 작동하는 방법을 알 필요가 없습니다.

방금 ​​fold을 cdr, car 및 rest으로 정의했습니다. 리치가 주장하는 것은 fold 그 자체가 그것이 작동하는 데이터 구조와는 별도의 추상 개념이며, 실제로 데이터 구조에서 작동하는 특정 기능을 제공하는 한 예상대로 작동한다는 것입니다.

그래서 궁극적으로는 관심사와 재사용 가능성을 분리하는 것입니다.

Answer 2

폴드는 귀납적 인 데이터 정의에 해당하기 때문에 원칙적으로 데이터 처리를위한 통일 ​​된 프레임 워크입니다. 그들은 특별하지 않습니다. cons/car/cdr은 데이터 (및 코드)를 작성하기위한 빌딩 블록이지만 비처방 방법은 아닙니다 (우리는 무엇이든 할 수 있고 그것을 임시로 처리 할 수 ​​있습니다). 겹은 더 높은 수준, 더 규율되고 예측 가능하며 추론하기 쉽습니다.

목록에 map, filter, mapcat에 대한 임시 구현이 주어지면 비슷한 구조가 있음을 알 수 있습니다. 데이터 구조를 따르는 코드 구조 (목록, 죄수 노드를 기반으로합니다. 결합 함수의 두 인수). 그리고 그것은 배입니다.

그 이야기에서 Rich Hickey는 단계 기능을 추상화합니다. 그러나 그는 데이터를 추상화하지 않습니다. 레이블이있는 나무를 접는 데 사용되는 결합 함수는 두 개가 아니라 세 개의 매개 변수를 사용해야합니다. 따라서 그의 -ing 함수가하는 일은 개념적으로 목록에서 접는 것입니다. 그것은 단지리스트의 구체적인 구현을 추상화하는 것입니다 - 단점 셀, 해시 된 배열 트리, 무엇이든간에.

Answer 3

불규칙한 언어로 된 대부분의 연산자에는 정의 할 수있는 파트너가 있으며, 그 반대의 경우도 마찬가지입니다. 이 속성을 "metacircularity"라고합니다. 언어가 제공하는 프로그래밍 기능의 전체 집합을 허용하는 기본적인 기본 연산자는 없습니다. http://home.pipeline.com/~hbaker1/MetaCircular.html