Перебрать набор функций с помощью Haskell

Принимая во внимание комментарий Дэниэлса, это может выглядеть примерно так:

f = loop init_a init_b true
    where
         loop a b True = loop a' b' (fun3 a' b')
             where
                 a' = fun1 ....
                 b' = fun2 .....
         loop a b False = (a,b)

Ну, вот предложение о том, как сопоставить понятия здесь:

• Цикл C++ — это некоторая форма операции со списком в Haskell.
• Одна итерация цикла = обработка одного элемента списка.
• Зацикливание до тех пор, пока определенное условие не станет истинным = базовый случай функции, которая рекурсивно работает со списком.

Но между императивными циклами и функциями функционального списка есть нечто существенное: циклы описывают как выполнять итерацию; функции списка более высокого порядка описывают структуру вычислений. Так, например, map f [a0, a1, ..., an] можно описать этой диаграммой:

[a0,   a1,   ..., an]
 |     |          |
 f     f          f
 |     |          |
 v     v          v
[f a0, f a1, ..., f an]

Обратите внимание, что это описывает, как результат связан с аргументами f и [a0, a1, ..., an], а не то, как итерация выполняется шаг за шагом.

Точно так же foldr f z [a0, a1, ..., an] соответствует этому:

f a0 (f a1 (... (f an z)))

filter не совсем подходит для построения диаграмм, но легко сформулировать множество правил, которым он удовлетворяет:

• length (filter pred xs) <= length xs
• Для каждого элемента x из filter pred xs pred x равно True.
• Если x является элементом filter pred xs, то x является элементом xs
• Если x не является элементом xs, то x не является элементом filter pred xs
• Если x появляется перед x' в filter pred xs, то x появляется перед x' в xs
• Если x появляется перед x' в xs, а x и x' появляются в filter pred xs, то x появляется перед x' в filter pred xs

В классической императивной программе все три случая записываются как циклы, и разница между ними сводится к тому, что делает тело цикла. Функциональное программирование, напротив, настаивает на том, что такого рода структурные паттерны не принадлежат «телам циклов» (функциям f и pred в этих примерах); скорее, эти шаблоны лучше всего абстрагировать в функции более высокого порядка, такие как map, foldr и filter. Таким образом, каждый раз, когда вы видите одну из этих функций списка, вы мгновенно узнаете некоторые важные факты о том, как связаны аргументы и результат, без необходимости читать какой-либо код; тогда как в типичной императивной программе вы должны прочитать тела циклов, чтобы понять это.

Таким образом, реальный ответ на ваш вопрос заключается в том, что невозможно предложить идиоматический перевод императивного цикла в функциональные термины, не зная, что делает тело цикла — какие предварительные условия должны быть до запуска цикла и какие предполагаются постусловия. быть, когда цикл заканчивается. Потому что это тело цикла, которое вы только расплывчато описали, будет определять структуру вычислений, и разные такие структуры будут вызывать разные функции более высокого порядка в Haskell.

Прежде всего, давайте подумаем о нескольких вещах.

• Есть ли у function1 побочные эффекты?
• Есть ли у function2 побочные эффекты?
• Есть ли у function3 побочные эффекты?

Ответом на все эти вопросы является совершенно очевидное ДА, потому что они не принимают никаких входных данных, и, по-видимому, существуют обстоятельства, которые заставляют вас проходить цикл while более одного раза (а не def function3(): return false). Теперь давайте переделаем эти функции с явным состоянием.

s = initialState
sentinel = true
while(sentinel):
  a,b,s,sentinel = function1(a,b,s,sentinel)
  a,b,s,sentinel = function2(a,b,s,sentinel)
  a,b,s,sentinel = function3(a,b,s,sentinel)
return a,b,s

Ну это довольно некрасиво. Мы абсолютно ничего не знаем ни о том, какие входные данные получает каждая функция, ни о том, как эти функции могут влиять на переменные a, b и sentinel, ни о «любом другом состоянии», которое я просто смоделировал как s.

Итак, давайте сделаем несколько предположений. Во-первых, я собираюсь предположить, что эти функции не зависят напрямую и никак не влияют на значения a, b и sentinel. Однако они могут изменить «другое состояние». Итак, вот что мы получаем:

s = initState
sentinel = true
while (sentinel):
  a,s2 = function1(s)
  b,s3 = function2(s2)
  sentinel,s4 = function(s3)
  s = s4
return a,b,s

Обратите внимание, что я использовал временные переменные s2, s3 и s4, чтобы указать изменения, через которые проходит "другое состояние". Время Хаскеля. Нам нужна управляющая функция, которая будет вести себя как цикл while.

myWhile :: s                   -- an initial state
        -> (s -> (Bool, a, s)) -- given a state, produces a sentinel, a current result, and the next state
        -> (a, s)              -- the result, plus resultant state
myWhile s f = case f s of
  (False, a, s') -> (a, s')
  (True,  _, s') -> myWhile s' f

Теперь, как можно использовать такую ​​функцию? Итак, учитывая, что у нас есть функции:

function1 :: MyState -> (AType, MyState)
function2 :: MyState -> (BType, MyState)
function3 :: MyState -> (Bool,  MyState)

Мы бы построили желаемый код следующим образом:

thatCodeBlockWeAreTryingToSimulate :: MyState -> ((AType, BType), MyState)
thatCodeBlockWeAreTryingToSimulate initState = myWhile initState f
  where f :: MyState -> (Bool, (AType, BType), MyState)
        f s = let (a, s2) = function1 s
                  (b, s3) = function2 s2
                  (sentinel, s4) = function3 s3
              in (sentinel, (a, b), s4)

Обратите внимание, как это похоже на неуродливый код, похожий на python, приведенный выше.

Вы можете убедиться, что код, который я представил, хорошо типизирован, добавив function1 = undefined и т. д. для трех функций, а также следующее в верхней части файла:

{-# LANGUAGE EmptyDataDecls #-}    
data MyState
data AType
data BType

Вывод таков: в Haskell вы должны явно моделировать изменения состояния. Вы можете использовать «монаду состояния», чтобы сделать вещи немного красивее, но сначала вы должны понять идею передачи состояния.

Давайте посмотрим на ваш цикл C++:

while (state == true) {
  a = function1();
  b = function2();
  state = function3();
}

Haskell — это чисто функциональный язык, поэтому он не будет так сильно ссориться с нами (и полученный код будет полезнее как сам по себе, так и в качестве упражнения для изучения Haskell), если мы попытаемся сделать это без побочных эффектов и без использования монады, чтобы выглядело так, как будто мы используем побочные эффекты.

Начнем с этой структуры

while (state == true) {
   <<do stuff that updates state>>
}

Очевидно, что в Haskell мы не собираемся проверять переменную на соответствие true как условию цикла, потому что она не может изменить свое значение[1], и мы либо оцениваем тело цикла навсегда, либо никогда. Поэтому вместо этого мы хотим оценить функцию, которая возвращает логическое значение для некоторого аргумента:

while (check something == True) {
  <<do stuff that updates state>>
}

Что ж, теперь у нас нет переменной state, так что «делать что-то, что обновляет состояние» выглядит довольно бессмысленно. И у нас нет something для перехода к check. Давайте подумаем об этом еще немного. Мы хотим, чтобы something зависело от того, что делает бит «делать вещи». У нас нет побочных эффектов, так что это означает, что something должен быть возвращен (или получен из него) из "делать вещи". «делать вещи» также должно принимать что-то, что варьируется в качестве аргумента, иначе он просто будет возвращать одно и то же навсегда, что также бессмысленно. Нам также нужно вернуть значение из всего этого, иначе мы просто сжигаем циклы процессора (опять же, без побочных эффектов нет смысла запускать функцию, если мы каким-то образом не используем ее вывод, и еще меньше смысла запускать функцию многократно, если мы никогда не используем ее вывод).

Итак, как насчет чего-то вроде этого:

while check func state =
    let next_state = func state in
    if check next_state
      then while check func next_state
      else next_state

Давайте попробуем это в GHCI:

*Main> while (<20) (+1) 0
20

Это результат многократного применения (+1), пока результат меньше 20, начиная с 0.

*Main> while ((<20) . length) (++ "zob") ""
"zobzobzobzobzobzobzob"

Это результат многократного объединения "zob", ​​когда длина результата меньше 20, начиная с пустой строки.

Итак, вы можете видеть, что я определил функцию, которая (немного) аналогична циклу while из императивных языков. Для этого нам даже не понадобился специальный синтаксис цикла! (что является реальной причиной того, что в Haskell нет такого синтаксиса; если вам нужны такие вещи, вы можете выразить их как функцию). Это не единственный способ сделать это, и опытные программисты на Haskell, вероятно, будут использовать другие стандартные библиотечные функции для выполнения такой работы, а не писать while.

Но я думаю, что полезно посмотреть, как вы можете выразить такие вещи в Haskell. Это показывает, что вы не можете перевести такие вещи, как императивные циклы, напрямую в Haskell; Я не стал переводить ваш цикл с точки зрения моего while, потому что это оказалось довольно бессмысленным; вы никогда не используете результат function1 или function2, они вызываются без аргументов, поэтому они всегда будут возвращать одно и то же на каждой итерации, а function3 также всегда возвращает одно и то же и может возвращать только true или false для любой причины while продолжать цикл или останавливаться без получения информации.

Предположительно, в программе на C++ все они используют побочные эффекты, чтобы действительно выполнить какую-то работу. Если они работают с вещами в памяти, вам нужно сразу перевести большую часть вашей программы в Haskell, чтобы перевод этого цикла имел какой-либо смысл. Если эти функции выполняют ввод-вывод, вам нужно будет сделать это в монаде IO в Haskell, для которой моя функция while не работает, но вы можете сделать что-то подобное.

[1] Кстати, стоит попытаться понять, что «вы не можете изменять переменные» в Haskell — это не просто произвольное ограничение и не просто приемлемый компромисс ради чистоты, это концепция, которая не имеет смысла, как Haskell хочет, чтобы вы думали о коде Haskell. Вы записываете выражения, полученные в результате вычисления функций с определенными аргументами: в f x = x + 1 вы говорите, что f x является x + 1. Если вы действительно думаете об этом таким образом, а не думаете, что «f берет x, затем добавляет к нему единицу, затем возвращает результат», тогда концепция «имеющих побочные эффекты» даже не применяется; как что-то существующее и равное чему-то другому может как-то изменить переменную или иметь какой-то другой побочный эффект?

Вы должны написать решение своей проблемы в более функциональном подходе. Однако некоторый код в Haskell работает во многом как императивный цикл, например, монады состояния, рекурсивность терминала, until, foldr и т. д.

Простой пример — факториал. В C вы бы написали цикл, где в haskell вы можете, например, написать fact n = foldr (*) 1 [2..n].

Если у вас есть две функции f :: a -> b и g :: b -> c, где a, b и c являются типами, подобными String или [Int], вы можете скомпоновать их, просто написав f . b.

Если вы хотите, чтобы они зацикливались на списке или векторе, вы можете написать map (f . g) или V.map (f . g), предполагая, что вы сделали Import qualified Data.Vector as V.

Пример: я хочу напечатать список заголовков уценки, таких как ## <number>. <heading> ##, но мне нужны римские цифры, пронумерованные от 1, а мой список headings имеет тип типа [(String,Double)], где Double не имеет значения.

Import Data.List
Import Text.Numeral.Roman
let fun = zipWith (\a b -> a ++ ". " ++ b ++ "##\n") (map toRoman [1..]) . map fst
fun [("Foo",3.5),("Bar",7.1)]

Что, черт возьми, это делает?

toRoman превращает число в строку, содержащую римскую цифру. map toRoman делает это с каждым элементом цикла. map toRoman [1..] делает это с каждым элементом ленивого бесконечного списка [1,2,3,4,..], давая ленивый бесконечный список строк римских цифр

fst :: (a,b) -> a просто извлекает первый элемент кортежа. map fst отбрасывает нашу глупую Meow информацию по всему списку.

\a b -> "##" ++ show a ++ ". " ++ b ++ "##" — это лямбда-выражение, которое берет две строки и объединяет их вместе в нужных строках форматирования.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c] принимает функцию с двумя аргументами, такую ​​как наше лямбда-выражение, и передает ей пары элементов из собственных второго и третьего аргументов.

Вы заметите, что zip, zipWith и т. д. считывают из ленивого бесконечного списка римских цифр столько, сколько необходимо для списка заголовков, то есть я пронумеровал свои заголовки, не сохраняя никаких переменных-счетчиков.

Наконец, я объявил fun без указания его аргумента, потому что компилятор может понять это из того факта, что map fst требует один аргумент. Вы заметите, что я поставил . перед моей второй картой. Я мог бы написать (map fst h) или $ map fst h вместо этого, если бы я написал fun h = ..., но отсутствие аргумента fun означало, что мне нужно составить его с zipWith после применения zipWith к двум аргументам из трех аргументов, которые нужны zipWith.

Я надеюсь, что компилятор объединит zipWith и map в один цикл с помощью встраивания.