Перевод императивного цикла for в идиоматический haskell
У меня есть некоторые трудности, чтобы перевести императивные алгоритмы в функциональный стиль. Основная идея, которую я не могу обернуть вокруг себя, заключается в том, как заполнять последовательности значениями в соответствии с их положением в последовательности. Как будет выглядеть идиоматическое решение для следующего алгоритма в Haskell?
A = unsigned char[256]
idx <- 1
for(i = 0 to 255)
if (some_condition(i))
A[i] <- idx
idx++
else
A[i] = 0;
Алгоритм в основном создает таблицу поиска для функции отображения гистограммы.
Знаете ли вы какие-либо ресурсы, которые помогли бы мне лучше понять эту проблему?
4 ответа
Одной из основных идей в функциональном программировании является выражение алгоритмов как преобразований данных. В ленивом языке, таком как Haskell, мы можем даже пойти на шаг дальше и думать о ленивых структурах данных как об усовершенствованных вычислениях. В реальном смысле списки на Haskell больше похожи на циклы, чем на обычные связанные списки: они могут быть вычислены постепенно и не должны существовать в памяти все сразу. В то же время мы все еще получаем множество преимуществ, связанных с наличием такого типа данных, как возможность передавать его и проверять с помощью сопоставления с образцом.
Имея это в виду, "трюк" для выражения цикла for с индексом состоит в создании списка всех значений, которые он может принимать. Ваш пример, вероятно, самый простой случай: i принимает все значения из 0 в 255, поэтому мы можем использовать встроенную нотацию Haskell для диапазонов:
[0..255]
На высоком уровне это эквивалент Хаскелла for (i = 0 to 255); затем мы можем выполнить реальную логику в цикле, обойдя этот список либо с помощью рекурсивной функции, либо функции более высокого порядка из стандартной библиотеки. (Второй вариант очень предпочтителен.)
Эта конкретная логика хорошо подходит для fold, Сгиб позволяет нам брать элемент списка за элементом и создавать какой-то результат. На каждом шаге мы получаем элемент списка и значение нашего результата. В данном конкретном случае мы хотим обработать список слева направо при увеличении индекса, поэтому мы можем использовать foldl; одна хитрость в том, что он создаст список в обратном направлении.
Вот тип foldl:
foldl :: (b -> a -> b) -> b -> [a] -> b
Таким образом, наша функция принимает наше промежуточное значение и элемент списка и создает обновленное промежуточное значение. Поскольку мы создаем список и отслеживаем индекс, нашим промежуточным значением будет пара, содержащая оба. Затем, как только мы получим окончательный результат, мы можем игнорировать idx Значение и обратный окончательный список мы получим:
a = let (result, _) = foldl step ([], 1) [0..255] in reverse result
where step (a, idx) i
| someCondition i = (idx:a, idx + 1)
| otherwise = (0:a, idx)
Фактически, шаблон преобразования списка при отслеживании некоторого промежуточного состояния (idx в этом случае) достаточно распространен, так что он имеет свою функцию с точки зрения State тип. Основная абстракция немного более сложна (прочитайте ["Вы могли бы изобрести монады"][вы] для хорошего введения), но полученный код на самом деле довольно приятен для чтения (за исключением импорта, я полагаю:P):
import Control.Applicative
import Control.Monad
import Control.Monad.State
a = evalState (mapM step [0..255]) 1
where step i
| someCondition i = get <* modify (+ 1)
| otherwise = return 0
Идея в том, что мы наносим на карту [0..255] отслеживая какое-то состояние (значение idx) на заднем фоне. evalState это то, как мы соединяем всю сантехнику вместе и просто получаем наш конечный результат. step Функция применяется к каждому элементу списка ввода, а также может получить доступ или изменить состояние.
Первый случай step функция интересная. <* Оператор говорит, что сначала нужно сделать что-то слева, что-то справа, но вернуть значение слева. Это позволяет нам получить текущее состояние, увеличить его, но при этом вернуть значение, которое мы получили до его увеличения. Тот факт, что наше понятие состояния является первоклассной сущностью, и мы можем иметь библиотечные функции, такие как <* очень мощный - я нашел этот конкретный идиом действительно полезным для обхода деревьев, и другие подобные идиомы были весьма полезны для другого кода.
Есть несколько способов решения этой проблемы в зависимости от того, какую структуру данных вы хотите использовать. Самый простой из них, вероятно, будет со списками и основными функциями, доступными в Prelude:
a = go 1 [] [0..255]
where
go idx out [] = out
go idx out (i:is) =
if condition i
then go (idx + 1) (out ++ [idx]) is
else go idx (out ++ [0]) is
Это использует рабочий шаблон с двумя аккумуляторами, idx а также out, и он обходит последний параметр до тех пор, пока не останется больше элементов, затем возвращает out, Это, безусловно, может быть преобразовано в fold какой-то, но в любом случае это будет не очень эффективно, добавляя элементы в список с ++ очень неэффективно. Вы могли бы сделать это лучше, используя idx : out а также 0 : outзатем с помощью reverse на выходе go, но это все еще не идеальное решение.
Другим решением может быть использование State монада:
a = flip runState 1 $ forM [0..255] $ \i -> do
idx <- get
if condition i
then do
put $ idx + 1 -- idx++
return idx -- A[i] = idx
else return 0
Который, безусловно, выглядит гораздо более настоятельным. 1 в flip runState 1 указывает, что ваше начальное состояние idx = 1тогда вы используете forM (который выглядит как цикл for, но на самом деле это не так) закончился [0..255]переменная цикла iи тогда это просто вопрос реализации остальной логики.
Если вы хотите пойти намного дальше, вы можете использовать StateT а также ST монады, чтобы иметь фактический изменяемый массив с состоянием в то же время. Объяснение того, как это работает, выходит далеко за рамки этого ответа, однако:
import Control.Monad.State
import Control.Monad.ST
import qualified Data.Vector as V
import qualified Data.Vector.Mutable as MV
a :: V.Vector Int
a = runST $ (V.freeze =<<) $ flip evalStateT (1 :: Int) $ do
a' <- lift $ MV.new 256
lift $ MV.set a' 0
forM_ [0..255] $ \i -> do
when (condition i) $ do
idx <- get
lift $ MV.write a' i idx
put $ idx + 1
return a'
Я немного упростил это, чтобы каждый элемент был установлен в 0 с самого начала, мы начинаем с начального состояния idx = 1зациклить [0..255], если текущий индекс i соответствует условию, то получить ток idx, запишите его в текущий индекс, затем увеличьте idx, Запустите это как операцию с состоянием, затем остановите вектор и, наконец, запустите ST монада сторона вещей. Это учитывает фактический изменчивый вектор, скрытый в пределах ST Монада, так что внешний мир не знает, что рассчитать a Вы должны сделать несколько довольно странных вещей.
Явная рекурсия:
a = go 0 1
where go 256 _ = []
go i idx | someCondition i = idx : go (i+1) (idx+1)
| otherwise = 0 : go (i+1) idx
Развертывание: (вариант явной рекурсии выше)
a = unfoldr f (0,1)
where f (256,_) = Nothing
f (i,idx) | someCondition i = Just (idx,(i+1,idx+1))
| otherwise = Just (0 ,(i+1,idx ))
Петли обычно можно выразить, используя разные fold функции. Вот решение, которое использует foldl(вы можете переключиться на foldl' если вы столкнетесь с ошибкой переполнения стека):
f :: (Num a) => (b -> Bool) -> a -> [b] -> [a]
f pred startVal = reverse . fst . foldl step ([], startVal)
where
step (xs, curVal) x
| pred x = (curVal:xs, curVal + 1)
| otherwise = (0:xs, curVal)
Как это использовать? Эта функция принимает предикат (someCondition в вашем коде), начальное значение индекса и список элементов для итерации. То есть можно позвонить f someCondition 1 [0..255] получить результат для примера из вашего вопроса.