Fold
(aka reduce
)은 매우 중요한 고차 함수로 간주됩니다. Map
은 fold
(see here)으로 나타낼 수 있습니다. 그러나 그것은 나에게 실제보다 학문적으로 들린다. 일반적인 사용은 합계, 곱 또는 최대 수를 얻을 수 있지만 이러한 함수는 대개 여러 인수를 허용합니다. 그렇다면 (+ 2 3 5)
이 정상적으로 작동 할 때 (fold + 0 '(2 3 5))
을 쓰는 이유는 무엇입니까? 제 질문은 어떤 상황에서 가장 쉽고 가장 자연 스럽습니까 fold
입니까?기능적 언어에서 fold/reduce의 실제 사용
답변
fold
의 요점은 더 추상적 점이다. 이전에는 할 수 없었던 일을 할 수있는 것이 아니라 더 쉽게 할 수 있다는 것입니다.
fold
을 사용하면 임의의 수의 요소에 적용되는 두 요소에 정의 된 함수를 일반화 할 수 있습니다. 두 개의 인수를 목록에 적용하는 단일 함수를 작성하고 테스트하고 유지 관리하고 수정하는 것이 일반적으로 훨씬 쉽기 때문에이 방법이 유리합니다. 비슷하지만,별로 기능이없는 2 개의 함수 대신 하나의 간단한 함수를 작성, 테스트, 유지 관리하는 것이 항상 쉽습니다. fold
(그리고 그 문제, map
, filter
및 친구) 동작을 잘 정의
때문에, 명시 적으로 재귀보다 이러한 기능을 사용하여 코드를 이해하는 것이 훨씬 쉽다.
기본적으로 한 버전을 사용하면 다른 버전을 무료로 사용할 수 있습니다. 궁극적으로 동일한 결과를 얻기 위해 더 적은 작업을 수행하게됩니다.
예제를 제공하지 않았지만 몇 가지 통찰력을 주셨습니다. 감사합니다. –
여기에 reduce
이 실제로 잘 작동하는 몇 가지 간단한 예가 있습니다.
각 부에서의 최대 값의 합을 찾기
Clojure에서 :
user=> (def x '((1 2 3) (4 5) (0 9 1)))
#'user/x
user=> (reduce #(+ %1 (apply max %2)) 0 x)
17
라켓 :
> (define x '((1 2 3) (4 5) (0 9 1)))
> (foldl (lambda (a b) (+ b (apply max a))) 0 x)
17
가리스트
에서지도를 구축Clojure의 : reduce
를 특징으로 더 복잡한의 Clojure 예를 들어
user=> (def y '(("dog" "bark") ("cat" "meow") ("pig" "oink")))
#'user/y
user=> (def z (reduce #(assoc %1 (first %2) (second %2)) {} y))
#'user/z
user=> (z "pig")
"oink"
는 프로젝트 오일러 문제 18 & 67에 my solution을 확인하십시오.
은 참조 : reduce vs. apply
예 :
(+ 2 3 4
)는 미리 인수의 개수를 알고 있기 때문에 작동합니다. 폴드는 크기가 다를 수있는 목록에서 작동합니다.fold
/reduce
은 "cdr-ing down a list"패턴의 일반 버전입니다. 시퀀스의 모든 요소를 순서대로 처리하고 그로부터 리턴 값을 계산하는 각 알고리즘은 함께 표현할 수 있습니다. 기본적으로 foreach 루프의 기능 버전입니다.
다음은 아직 언급하지 않은 예입니다.
"fold"와 같이 작고 잘 정의 된 인터페이스가있는 함수를 사용하면이를 사용하는 프로그램을 손상시키지 않고 해당 구현을 바꿀 수 있습니다. 예를 들어, distributed version that runs on thousands of PCs을 만들 수 있으므로이를 사용하는 정렬 알고리즘은 distributed sort이됩니다. 귀하의 프로그램은 more robust, simpler, and faster이됩니다.
예제는 간단한 것입니다. +
은 이미 인수를 취하고, 작은 메모리에서 빠르게 실행되며, 컴파일러를 작성한 사람이 이미 작성하고 디버깅했습니다. 이러한 속성은 종종 실행해야하는 알고리즘에 해당하지 않습니다.
코드를 사용하는 코드는 읽기가 일반적으로 어렵습니다. 그래서 사람들은 가능한 경우지도, 필터, 존재, 합계 등을 선호합니다 (—). 요즘 저는 주로 컴파일러와 통역사를 씁니다. 여기에 몇 가지 방법이다 나는 배 사용
- 계산 기능, 표현의 자유 변수의 설정, 또는
- 는
- 컬렉션을 축적 확인 유형, 예를 들면 심볼 테이블에 함수의 매개 변수를 추가 입력 정의의 순서에서 생성 된 모든 분별 오류 메시지의
- 부팅시 스몰 토크 인터프리터 모든 미리 정의 된 클래스를 추가 모든 용도의 공통점은 무엇
은 그 시퀀스에 대한 정보가 또는 사전으로 설정되어 있습니다. 현저하게 실용적입니다.
공통 Lisp 함수에서는 여러 인수를 허용하지 않습니다.
모든 Common Lisp 구현 CALL-ARGUMENTS-LIMIT에 정의 된 상수가 50 이상이어야합니다.
이것은 이식 가능한 모든 함수가 적어도 50 개의 인수를 받아 들여야 함을 의미합니다. 그러나 이것은 단지 50 일 수 있습니다.
이 제한은 컴파일러가 최적화 된 호출 스키마를 사용하고 무제한의 인수가 전달 될 수있는 일반적인 경우를 제공하지 못하게하기 위해 존재합니다.
따라서 휴대형 Common Lisp 코드에서 커다란 (50 개보다 큰) 목록이나 벡터를 처리하려면 iteration constructs, reduce, map 및 이와 유사한 것을 사용해야합니다. 따라서 (apply '+ large-list)
을 사용하지 말고 (reduce '+ large-list)
을 사용해야합니다.
'+'가 이미 2 개 이상의 인수를 허용하지 않은 경우 어떻게 구현합니까? – Gabe
'fold'는'map'과 같은 많은 상위 수준의 유용한 함수들을위한 빌딩 블록입니다. 당신의 프로그램은 원래'fold '보다는 그 기능을 사용하는 경향이 있지만 목록을 일종의 fold로 사용하는 거의 모든 기능을 구현할 수 있다는 사실은 매우 중요합니다. – dfan