Die Mechanik von fold_right verstehen

Question

Problem: Definieren Sie die Funktion mapf, deren erstes Argument eine unäre Funktion und zweite Argumentliste ist. Das Ergebnis ist eine Liste der Funktionen, die auf jedes Element der Argumentliste angewendet werden. Schreiben Sie einen Einzeiler mit fold_right und nicht mit einer rekursiven Funktion.

Lösung:

let mapf fn list = fold_right (fun h t -> fn h :: t) list [] 

Ich verstehe nicht, wie das löst das Problem, weil fold_right eine Funktion mit der Liste Argumenten in einer rekursiven Art und Weise berechnet, so gibt sie einen Wert und nicht um eine Liste. Ich verstehe auch nicht, was die folgende Notation bedeutet:

fun h t -> fn h :: t 

Answer 1

Ihre beiden Fragen sind verwandt. Es stimmt, dass fold_right einen Wert zurückgibt, aber eine Liste ist ein Wert! Der :: Operator fügt ein neues Element am Anfang einer Liste hinzu. Also ist der Wert, der durch diese Anwendung von fold_right berechnet wird, tatsächlich eine Liste.

Eine andere Möglichkeit, dies zu denken, könnte wie folgt aussehen. Wenn Sie fold_right mit dem + Operator berechnen Sie einen Wert wie so:

fold_right (+) [1; 2; 3] 0 => 
1 + 2 + 3 + 0 => 
6 

Wenn Sie fold_right mit dem :: Operator verwenden, berechnen Sie einen Wert wie so:

fold_right (::) [1; 2; 3] [] => 
1 :: 2 :: 3 :: [] => 
[1; 2; 3] 

Dies ist nicht theoretisch es funktioniert genau wie dies in der REPL:

# List.fold_right (+) [1; 2; 3] 0;; 
- : int = 6 
# List.fold_right (fun a b -> a :: b) [1; 2; 3] [];; 
- : int list = [1; 2; 3] 

(Sie müssen fun a b -> a :: b schreiben, weil t Die :: Notation kann nicht als Standalone-Funktion verwendet werden. Leider)

Beachten Sie, dass es völlig legitim ist eine Liste mit dem :: Betreiber selbst zu schreiben.

# 1 :: 2 :: 3 :: [];; 
- : int list = [1; 2; 3] 

aktualisiert

Zuerst fun x y -> expr ist die Bezeichnung für ein "Lambda" in OCaml, dh für ein Funktionsliteral. Die Funktion fun h t -> fn h :: t benötigt zwei Werte h und t. Er wendet die Funktion fn auf h an und gibt eine neue Liste mit diesem neuen Wert an der Vorderseite von t zurück.

Aus Typisierung Sicht der Wert h muss die richtige Art zu fn, passiert und fn muss einen Wert des richtigen Typs zurückgeben t in der Liste zu sein.

Sie könnten es in Klammern setzen wie folgt: fun h t -> (fn h) :: t, wenn das es klarer macht. Die Funktion fun a b -> a :: b ist ähnlich, außer dass sie a direkt in die Liste b einfügt. Es wendet keine Funktion an.Im Wesentlichen macht es genau das, was der :: Operator tut.

Schreibweise muss a der richtige Typ sein, um ein Element der Liste b zu sein.

Update 2

Wenn Sie zu verstehen sind versuchen, was ein Lambda ist, besteht eine Möglichkeit, es zu betrachten ist, dass es nur eine praktische Möglichkeit, eine Funktion zu schreiben, die relativ klein ist. Sie können Ihre gegebenen Code ohne Lambda leicht schreiben:

let mapf fn list = 
    let helper h t = fn h :: t in 
    List.fold_right helper list [] 

Statt einer Lambda, diese Version hat eine lokal deklarierten Funktion namens helper.

Eine andere Art zu betrachten ist, dass alle Funktionen Lambdas sind. Der idiomatische Weg, um eine Funktion zu schreiben:

let f x y = x + y 

ist nur eine praktische Abkürzung für eine Version mit einem expliziten Lambda:

let f = fun x y -> x + y 

Also, wirklich, ein Lambda ist nicht eine besondere Art von Funktion. Es ist genau wie jede andere Funktion. Es ist nur eine Notationswahl.