Список функциональных фрагментов кода для процедурных программистов?

Question

Иногда я все еще застреваю, пытаясь перевести процедурный код в функциональный код.

Есть ли список функциональных идиом/фрагментов, которые сопоставляются с процедурными идиомами/фрагментами?

Редактировать

Поскольку не кажется, централизованный сайт этих фрагментов, я превращаю это в вики сообщества. Пожалуйста, вставьте здесь любые процедурные -> функциональные фрагменты.

Answer 1

(ред от this post на fshub)

Первый раз, когда я пошел, чтобы достигнуть перерыва/продолжить в OCaml/F #, он бросил меня на (бесконечная), так сказать, потому что такого не существует! В OCaml можно использовать исключения для выхода из цикла, потому что они очень дешево, но в F # (in.NET) накладные расходы достаточно высоки и не полезны для «нормального» управления потоком.

Это произошло, когда вы играли с алгоритмами сортировки некоторое время назад (чтобы убить некоторое время), которые сильно используют повтор/пока и не сломаются. Меня поразило то, что рекурсивные функции вызова хвоста могут достичь точно такого же результата, только с легким умением до читаемости. Итак, я выбросил «изменчивый bDone» и «пока не bDone» и попытался написать код без этих императивных конструкций. Ниже перечислены только фрагменты цикла и показано, как писать повтор/пока, do/while, while/do, break/continue и test-in-the-middle стиль кода с использованием tailcalls. Кажется, что все они работают с той же скоростью, что и обычный оператор F # 'while', но ваш пробег может отличаться (некоторые платформы могут неправильно реализовать tailcall и, следовательно, могут сбрасывать ошибки до тех пор, пока они не будут исправлены). В конце для сравнения используется алгоритм (плохой) сортировки, написанный в обоих стилях.

Начнем с цикла «do/while», написанного в традиционном стиле F #, а затем рассмотрим функциональные вариации, которые обеспечивают как цикл одного типа, так и различные семантики, такие как while/do, repeat/until, тест в середине и даже break/continue (без monads .. um, workflows!).

#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 

Хорошо, это достаточно легко. Имейте в виду, что f() всегда вызывается хотя бы один раз (do/while).

Вот такой же код, но в функциональном стиле. Обратите внимание: нам не нужно объявлять здесь mutable.

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

Мы можем открутить это до традиционного do/while путем помещения вызова функции внутри блока if.

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

Как насчет повторения блока до тех пор, пока не будет выполнено какое-либо условие (повторите/пока)? Достаточно легко ...

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

Что это было за прерывание без монады? Ну, просто введите условное выражение, которое возвращает «единица», как в:

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

Как насчет продолжения? Ну, это просто еще один звонок в петлю! Во-первых, с синтаксической костыль:

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'() 

И опять без (уродливой) синтаксиса костыль:

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() 

легко, как пирог!

Одним из приятных результатов этих форм цикла является то, что он упрощает определение и реализацию состояний в ваших циклах. Например, сортировка пузырьков непрерывно циклически перемещается по всему массиву, заменяя значения, которые неуместны по мере их нахождения. Он отслеживает, прошел ли пропуск по массиву любые обмены. Если нет, то каждое значение должно быть в нужном месте, поэтому сортировка может завершиться. В качестве оптимизации на каждом проходе через массив последнее значение в массиве заканчивается сортировкой в ​​нужное место. Таким образом, цикл может быть сокращен каждый раз через. Большинство алгоритмов проверяют своп и обновляют флаг «bModified» каждый раз, когда он есть. Однако, как только первый обмен выполняется, нет необходимости в этом назначении; он уже установлен в true!

Вот код F #, который реализует сортировку пузырьков (да, тип пузыря - это ужасный алгоритм, быстрая сортировка камней). В конце - императивная реализация, которая не меняет состояние; он обновляет флаг bModified для каждого обмена.Интересно, что императивное решение быстрее на крошечных массивах и на два процента меньше на больших. (Сделано для хорошего примера, хотя).

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

О, теперь это отличный вопрос. Вот некоторые, code snips in python или что-то Хлоя:

• для петель можно заменить итераторы

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

• для петель можно заменить применить или карту или фильтр

  map (верхний, ['предложение', 'фрагмент']) [ 'ПРИГОВОР', 'ФРАГМЕНТ']

• вложенный для петель с составом функций

• хвоста рекурсией вместо петель

• генератор выражение в месте для петель

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

Answer 3

Старый домашнее задание вопрос:

Функция

(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))) 

в типичном императивном стиле, с назначением и зацикливание. Напишите эквивалентную функцию f-функционала, которая не использует начальные функции (секвенирование) императива, while (goto) и set (назначение). Вы можете использовать столько «вспомогательных функций», сколько хотите, если они определены с помощью let или letrec, а не на верхнем уровне.

Одно из решений:

; 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

Сложение - очень интересная функция, которая является центральной во многих функциональных алгоритмах. Предположим, мы хотим добавить все элементы списка. В процедурном коде вы обычно создаете переменную аккумулятора и устанавливаете ее в 0, затем перебираете по списку и увеличиваете аккумулятор на элемент.

В OCaml, необходимо выполнить те же действия в функциональном способом, используя складка:

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

Используя раз, вы можете, например, подсчитать количество слов в списке и сцепить их в то же время:

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

Другим полезным использованием складок является копирование вектора в набор. Поскольку наборы в Ocaml неизменяемы, вам действительно необходимо создать для каждого элемента списка новый набор, содержащий предыдущий набор плюс этот новый элемент.

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] 

Здесь наш исходный объект является пустым множеством, и при каждом вызове, новый набор будет создан, на основе предыдущего набора и текущий элемент с использованием IntSet.add.

Реализовать рекурсивно один раз, чтобы узнать, как это делается под капотом, а затем использовать встроенную версию везде. Даже в C++, с std::accumulate!

Answer 5

Проект PLEAC имеет почти все это в качестве своей цели - реализовать все примеры в поварской книге perl на других языках. Вот ссылки на версию ocaml (которая является одной из трех 100% полной) http://pleac.sourceforge.net/pleac_ocaml/index.html