Danh sách các đoạn mã chức năng cho các lập trình viên thủ tục?

Question

Đôi khi tôi vẫn gặp khó khăn khi cố dịch mã thủ tục thành mã chức năng.

Có danh sách các thành phần/đoạn mã chức năng được ánh xạ tới thành ngữ/đoạn mã thủ tục không?

Sửa

Vì có dường như không phải là một trang web tập trung của những đoạn, tôi quay này thành một cộng đồng wiki. Vui lòng dán bất kỳ thủ tục -> đoạn mã chức năng nào tại đây.

Answer 1

(Sửa từ this post trên fshub)

Lần đầu tiên tôi đã đi để đạt được cho nghỉ/tiếp tục trong OCaml/F #, nó ném tôi cho một (vô hạn) vòng lặp, do đó, để nói chuyện, bởi vì không có điều như vậy tồn tại! Trong OCaml, người ta có thể sử dụng ngoại lệ để thoát khỏi vòng lặp vì chúng là rất giá rẻ, nhưng trong F # (in.NET) chi phí khá cao và không hữu ích cho việc kiểm soát luồng "bình thường".

Điều này xuất hiện khi chơi với thuật toán sắp xếp một thời gian trở lại (để giết thời gian), sử dụng nhiều lần lặp lại/cho đến khi và ngắt. Nó đánh tôi rằng các hàm gọi đệ quy đuôi có thể đạt được kết quả tương tự, chỉ với một chút ding để dễ đọc. Vì vậy, tôi đã ném ra 'mutable bDone' và 'while not bDone' và cố gắng viết mã mà không có những cấu trúc bắt buộc này. Các phần sau chỉ ra các phần lặp và cho thấy cách viết lặp lại/cho đến khi, làm/while, trong khi/do, ngắt/tiếp tục và mã kiểu thử nghiệm ở giữa bằng cách sử dụng các ổ đĩa. Tất cả những điều này xuất hiện để chạy với tốc độ tương tự như câu lệnh truyền thống F # 'while', nhưng số dặm của bạn có thể thay đổi (một số nền tảng có thể không thực hiện đúng tailcall và do đó có thể ngăn lỗi cho đến khi chúng được vá). Cuối cùng là một thuật toán sắp xếp (xấu) được viết bằng cả hai kiểu, để so sánh. Hãy bắt đầu với một vòng lặp 'do/while', được viết theo kiểu F # truyền thống, sau đó xem xét các biến thể chức năng cung cấp cả cùng một loại vòng lặp, cũng như ngữ nghĩa khác nhau như trong khi/làm, lặp lại/cho đến khi, kiểm tra ở giữa, và thậm chí phá vỡ/tiếp tục (không có monads .. um, quy trình công việc!).

#light 
(* something to work on... *) 
let v = ref 0 
let f() = incr v; 
let g() = !v; 
let N = 100000000 

let imperDoWhile() = 
    let mutable x = 0 
    let mutable bDone = false 
    while not bDone do 
     f() 
     x <- x + 1 
     if x >= N then bDone <- true 

Ok, thật dễ dàng. Hãy nhớ rằng f() luôn được gọi ít nhất một lần (do/while).

Đây là cùng mã, nhưng theo kiểu chức năng. Lưu ý rằng chúng tôi không cần khai báo một biến thể ở đây.

let funDoWhile() = 
    let rec loop x = 
     f()    (*Do*) 
     if x < N then (*While*) 
      loop (x+1) 
    loop 0 

Chúng tôi có thể quay điều đó sang kiểu truyền thống/trong khi bằng cách thực hiện cuộc gọi hàm bên trong khối if.

let funWhileDo() = 
    let rec loop x = 
     if x < N then (*While*) 
      f()   (*Do*) 
      loop (x+1) 
    loop 0 

Làm thế nào để lặp lại khối cho đến khi một số điều kiện là đúng (lặp lại/đến)? Đủ dễ dàng ...

let funRepeatUntil() = 
    let rec loop x = 
     f()     (*Repeat*) 
     if x >= N then() (*Until*) 
     else loop (x+1) 
    loop 0 

Điều gì đã xảy ra trong thời gian nghỉ ngắn hơn? Vâng, chỉ cần giới thiệu một biểu thức có điều kiện trả về 'đơn vị', như trong:

let funBreak() = 
    let rec loop() = 
     let x = g() 
     if x > N then() (*break*) 
     else 
      f() 
      loop() 
    loop() 

Còn tiếp tục? Vâng, đó chỉ là một cuộc gọi khác để lặp lại! Thứ nhất, với một cái nạng cú pháp:

let funBreakContinue() = 
    let break'() =() 
    let rec continue'() = 
     let x = g() 
     if x > N then break'() 
     elif x % 2 = 0 then 
      f(); f(); f(); 
      continue'() 
     else 
      f() 
      continue'() 
    continue'() 

Và sau đó một lần nữa mà không (xấu xí) cú pháp cái nạng:

let funBreakContinue'() = 
    let rec loop() = 
     let x = g() 
     if x > N then() 
     elif x % 2 = 0 then 
      f(); f(); f(); 
      loop() 
     else 
      f() 
      loop() 
    loop() 

dễ dàng như chiếc bánh!

Một kết quả tốt đẹp của các biểu mẫu vòng lặp này là giúp dễ dàng phát hiện và triển khai các trạng thái trong vòng lặp của bạn. Ví dụ: loại bong bóng liên tục lặp lại trên toàn bộ mảng, trao đổi các giá trị không phù hợp khi tìm thấy chúng. Nó theo dõi xem việc vượt qua mảng có tạo ra bất kỳ trao đổi nào hay không. Nếu không, thì mọi giá trị phải ở đúng nơi, do đó sắp xếp có thể chấm dứt. Là một tối ưu hóa, trên mỗi lần truyền thông qua mảng, giá trị cuối cùng trong mảng kết thúc được sắp xếp vào đúng vị trí. Vì vậy, vòng lặp có thể được rút ngắn từng cái một. Hầu hết các thuật toán kiểm tra trao đổi và cập nhật cờ "bModified" mỗi khi có. Tuy nhiên, một khi việc hoán đổi đầu tiên được thực hiện, không cần phải có nhiệm vụ đó; nó đã được đặt thành true!

Dưới đây là mã F # thực hiện một loại bong bóng (có, loại bong bóng là thuật toán khủng khiếp, đá quicksort). Cuối cùng là một thực thi bắt buộc mà không thay đổi trạng thái; nó cập nhật cờ bModified cho mọi trao đổi.Điều thú vị là giải pháp bắt buộc nhanh hơn trên các mảng nhỏ và chỉ chậm hơn một hoặc hai phần trăm trên các mảng lớn. (Thực hiện cho một ví dụ tốt, mặc dù).

let inline sort2 f i j (a:'a array) = 
    let i' = a.[ i ] 
    let j' = a.[ j ] 
    if f i' j' > 0 then 
     a.[ i ] <- j' 
     a.[ j ] <- i' 

let bubble f (xs:'a array) = 
    if xs.Length = 0 
    then() 

    let rec modified i endix = 
     if i = endix then 
      unmodified 0 (endix-1) 
     else 
      let j = i+1 
      sort2 f i j xs 
      modified j endix 
    and unmodified i endix = 
     if i = endix then 
      () 
     else 
      let j = i+1 
      let i' = xs.[ i ] 
      let j' = xs.[ j ] 
      if f i' j' > 0 then 
       xs.[ i ] <- j' 
       xs.[ j ] <- i' 
       modified j endix 
      else 
       unmodified j endix 
    in unmodified 0 (xs.Length-1) 

let bubble_imperitive f (xs:'a array) = 
    let mutable bModified = true 
    let mutable endix = xs.Length - 1 
    while bModified do 
     bModified <- false 
     endix <- endix - 1 
     for i in 0..endix do 
      let j = i+1 
      let i' = xs.[ i ] 
      let j' = xs.[ j ] 
      if f i' j' > 0 then 
       xs.[ i ] <- j' 
       xs.[ j ] <- i' 
       bModified <- true 
     done 
    done 

Answer 2

Ồ, bây giờ đây là một câu hỏi tiện lợi. Dưới đây là một số người, code snips in python hoặc một cái gì đó Cloe:

• cho vòng có thể được thay thế bằng vòng lặp

  stripped_list = [line.strip() for line in line_list]

• cho vòng có thể được thay thế bằng áp dụng hoặc bản đồ hoặc lọc

  bản đồ (trên, ['câu', 'đoạn']) [ 'câu', 'mảnh']

• lồng cho vòng với thành phần của chức năng

• đệ quy đuôi ở vị trí của vòng

• biểu thức máy phát điện ở vị trí của cho vòng

  sum(x*x for x in range(10))

Answer 3

Cũ bài tập câu hỏi:

Chức năng

(define f-imperative (y) (x) ; x is a local variable 
    (begin 
    (set x e) 
    (while (p x y) 
     (set x (g x y))) 
    (h x y))) 

là trong một phong cách bắt buộc điển hình, với nhiệm vụ và vòng lặp. Viết hàm f tương đương chức năng không sử dụng các tính năng bắt buộc (bắt đầu), trong khi (goto) và đặt (gán). Bạn có thể sử dụng nhiều hàm `helper 'như bạn muốn, miễn là chúng được định nghĩa bằng cách sử dụng let hoặc letrec và không ở mức cao nhất.

Một giải pháp:

; The idea is simple: 
; Use parameter passing for binding the values 
; of the variables and recursion instead of iteration. 
; 
; For those who like theory this is the main argument for proving 
; that recursive functions (LISP, lambda calculus) have the same 
; computational power as any imperative programming language. 

(define f-functional (y) 
    (letrec (
    (f-helper (lambda (x y) 
        (if (p x y) 
        (f-helper (g x y) y) 
        (h x y))))) 
    (f-helper e y))) 

; Notice that y in f-helper is invariant. Therefore, we can rewrite 
; f-helper without y as follows. 

(define f-functional (y) 
    (letrec (
    (f-helper (lambda (x) 
        (if (p x y) 
        (f-helper (g x y)) 
        (h x y))))) 
    (f-helper e))) 

; This is not the only solution, though I think it is one of the 
; nicer ones. 

Answer 4

Lần gấp là một chức năng rất thú vị, đó là trung tâm trong nhiều thuật toán chức năng. Giả sử chúng ta muốn thêm tất cả các phần tử của danh sách. Trong mã thủ tục, bạn thường sẽ tạo một biến tích lũy và đặt nó thành 0, sau đó lặp qua danh sách và tăng bộ tích lũy của mục.

Trong Ocaml, bạn thực hiện các hành động tương tự một cách chức năng bằng cách sử dụng gấp:

List.fold_left (+) 0 [1; 2; 3];; 
- : int = 6 

Sử dụng gấp, bạn có thể ví dụ đếm số từ trong danh sách và ghép chúng cùng một lúc:

List.fold_left (fun (count, concat) e -> (count + 1, concat^e)) (0, "") ["a"; "b"; "c"];; 
- : int * string = (3, "abc") 

Một cách sử dụng hữu ích khác là sao chép vectơ vào bộ. Vì các bộ trong Ocaml là bất biến, bạn cần phải tạo cho từng mục trong danh sách một tập hợp mới chứa tập hợp trước đó cộng với mục mới đó.

module Int = struct type t = int let compare = compare end;; 
module IntSet = Set.Make(Int);; 

let s = List.fold_left (fun set e -> IntSet.add e set) IntSet.empty [1; 2; 3];; 
val s : IntSet.t = <abstr> 

IntSet.elements s;; 
- : IntSet.elt list = [1; 2; 3] 

Ở đây, đối tượng ban đầu của chúng tôi là một tập rỗng, và tại mỗi cuộc gọi, một bộ mới được tạo ra, dựa trên các thiết lập trước và mục hiện tại bằng cách sử dụng IntSet.add.

Thực hiện gập đệ quy một lần, để biết cách thực hiện nó dưới mui xe, sau đó sử dụng phiên bản tích hợp ở mọi nơi. Ngay cả trong C++, với std::accumulate!

Answer 5

Dự án PLEAC gần như chính xác như mục tiêu của nó - thực hiện tất cả các ví dụ trong sách dạy nấu ăn theo ngôn ngữ khác. Dưới đây là các liên kết đến phiên bản ocaml (là một trong ba 100% hoàn thành) http://pleac.sourceforge.net/pleac_ocaml/index.html