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

Question

Вот простой, простой пример того, как код, который я пытаюсь сделать, будет выглядеть в C ++.

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

В программе, над которой я работаю, у меня есть некоторые функции, которые мне нужно пройти по циклу, пока bool состояние не станет равным false (или пока одна из переменных, скажем, переменная b, не станет равной 0).

Как этот код будет сделан в Haskell? Я искал здесь, в Google и даже в Bing, и не смог найти четких, понятных объяснений о том, как выполнять повторяющиеся действия с функциями.

Любая помощь будет оценена.

Answer 1

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

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)

Answer 2

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

• Цикл 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.

Answer 3

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

• Есть ли у 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 вы должны явно смоделировать изменения в состоянии.Вы можете использовать «Государственную монаду», чтобы сделать вещи немного красивее, но сначала вы должны понять идею передачи состояния вокруг.

Answer 4

Давайте посмотрим на ваш цикл 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 должен быть (или получен из) возвращен из "do stuff". «делать вещи» также нужно принимать что-то, что варьируется в качестве аргумента, или просто будет продолжать возвращать одно и то же навсегда, что также бессмысленно. Мы также должны вернуть значение из всего этого, в противном случае мы просто сжигаем циклы ЦП (опять же, без побочных эффектов, нет смысла запускать функцию, если мы каким-либо образом не используем ее вывод, а еще меньше - запускать функцию). функция, если мы никогда не используем ее вывод).

Так как насчет этого:

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; Я не стал переводить ваш цикл в терминах моего while, потому что он заканчивается довольно бессмысленно; вы никогда не используете результат function1 или function2, они вызываются без аргументов, поэтому они всегда возвращают одно и то же в каждой итерации, а function3 также всегда возвращает одно и то же и может возвращать только true или false, чтобы либо while продолжал цикл или останавливался, без информации.

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

---

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

Answer 5

Если у вас есть две функции 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 s в один цикл с помощью встраивания.

Answer 6

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

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