[f#] 접기와 축소의 차이점은 무엇입니까?

Program / 글쓴이

F #을 배우려고하지만 fold 와 reduce 를 구별하려고 할 때 혼란스러워졌습니다 . 접기는 같은 일 을하는 것처럼 보이지만 추가 매개 변수를 사용합니다. 이 두 기능이 존재하는 합법적 인 이유가 있거나 다른 배경을 가진 사람들을 수용 할 수있는 이유가 있습니까? (예 : C #의 문자열 및 문자열)

다음은 샘플에서 복사 한 코드 스 니펫입니다.

let sumAList list =
    List.reduce (fun acc elem -> acc + elem) list

let sumAFoldingList list =
    List.fold (fun acc elem -> acc + elem) 0 list

printfn "Are these two the same? %A "
             (sumAList [2; 4; 10] = sumAFoldingList [2; 4; 10])

답변

Foldreduce입력 목록의 첫 번째 요소를 초기 누산기 값으로 사용하는 동안 누산기에 대한 명시적인 초기 값을 사용합니다.

즉, 누산기 및 결과 유형이 목록 요소 유형과 일치해야하지만 fold누산기가 별도로 제공되므로 다를 수 있습니다 . 이것은 유형에 반영됩니다.

List.fold : ('State -> 'T -> 'State) -> 'State -> 'T list -> 'State
List.reduce : ('T -> 'T -> 'T) -> 'T list -> 'T

또한 reduce빈 입력 목록에서 예외가 발생합니다.

답변

리는 말 이외에, 당신은 정의 할 수 reduce의 관점에서 fold(쉽게) 다른 방법 내내 있지만 :

let reduce f list =
  match list with
  | head::tail -> List.fold f head tail
  | [] -> failwith "The list was empty!"

fold누산기에 대해 명시적인 초기 값을 취 한다는 사실은 또한 fold함수 의 결과가 목록의 값 유형과 다른 유형을 가질 수 있음을 의미 합니다. 예를 들어, 유형의 누산기를 사용 string하여 목록의 모든 숫자를 텍스트 표현으로 연결할 수 있습니다 .

[1 .. 10] |> List.fold (fun str n -> str + "," + (string n)) ""

를 사용할 때 reduce누산기 유형은 목록의 값 유형과 동일합니다. 즉, 숫자 목록이있는 경우 결과는 숫자 여야합니다. 이전 샘플을 구현하려면 숫자를 string첫 번째 로 변환 한 다음 누적해야합니다.

[1 .. 10] |> List.map string
          |> List.reduce (fun s1 s2 -> s1 + "," + s2)

답변

그들의 서명을 살펴 보자 :

> List.reduce;;
val it : (('a -> 'a -> 'a) -> 'a list -> 'a) = <fun:clo@1>
> List.fold;;
val it : (('a -> 'b -> 'a) -> 'a -> 'b list -> 'a) = <fun:clo@2-1>

몇 가지 중요한 차이점이 있습니다.

  • reduce한 가지 유형의 요소에서만 작동 하지만 의 누산기 및 목록 요소 fold는 다른 유형일 수 있습니다.

  • 를 사용 하면 첫 번째부터 시작하는 모든 목록 요소에 reduce함수 f를 적용합니다 .

    f (... (f i0 i1) i2 ...) iN.

    를 사용 하면 누산기부터 fold적용 f합니다 s.

    f (... (f s i0) i1 ...) iN.

따라서, reduce결과 ArgumentException빈 목록. 또한 fold보다 일반적입니다 reduce. 당신이 사용할 수있는 fold구현하기 reduce쉽게.

어떤 경우에는 사용 reduce이 더 간결합니다.

// Return the last element in the list
let last xs = List.reduce (fun _ x -> x) xs

합리적인 누산기가 없으면 더 편리합니다.

// Intersect a list of sets altogether
let intersectMany xss = List.reduce (fun acc xs -> Set.intersect acc xs) xss

일반적으로 fold임의 유형의 누산기를 사용하면 더 강력합니다.

// Reverse a list using an empty list as the accumulator
let rev xs = List.fold (fun acc x -> x::acc) [] xs

답변

fold은보다 훨씬 더 가치있는 기능 reduce입니다. 에서 다양한 기능을 정의 할 수 있습니다 fold.

reduce의 하위 집합입니다 fold.

접기의 정의 :

let rec fold f v xs =
    match xs with
    | [] -> v
    | (x::xs) -> f (x) (fold f v xs )

접기로 정의 된 함수의 예 :

let sum xs = fold (fun x y -> x + y) 0 xs

let product xs = fold (fun x y -> x * y) 1 xs

let length xs = fold (fun _ y -> 1 + y) 0 xs

let all p xs = fold (fun x y -> (p x) && y) true xs

let reverse xs = fold (fun x y -> y @ [x]) [] xs

let map f xs = fold (fun x y -> f x :: y) [] xs

let append xs ys = fold (fun x y -> x :: y) [] [xs;ys]

let any p xs = fold (fun x y -> (p x) || y) false xs

let filter p xs =
    let func x y =
        match (p x) with
        | true -> x::y
        | _ -> y
    fold func [] xs

답변