Передача императива для цикла в идиоматический haskell

Question

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

A = unsigned char[256] 
idx <- 1 
for(i = 0 to 255) 
    if (some_condition(i)) 
     A[i] <- idx 
     idx++ 
    else 
     A[i] = 0; 

Алгоритм в основном создает таблицу поиска для функции отображения гистограммы.

Знаете ли вы какие-либо ресурсы, которые помогут мне лучше понять эту проблему?

Answer 1

Одна из основных идей в функциональном программировании, чтобы выразить алгоритмы, как данных преобразований. На ленивом языке, таком как Haskell, мы можем пойти еще дальше и подумать о ленивых структурах данных как о reified вычислениях. В очень реальном смысле списки Haskell больше похожи на циклы, чем на обычные связанные списки: они могут быть вычислены постепенно и не обязательно должны существовать в памяти сразу. В то же время мы по-прежнему получаем много преимуществ наличия такого типа данных, как эта способность передавать его и проверять его с помощью сопоставления с образцом.

Учитывая это, «трюк» для выражения цикла for с индексом - это создать список всех значений, которые он может принять. Ваш пример, вероятно, самый простой случай: i принимает все значения от 0 до 255, поэтому мы можем использовать встроенные обозначения Хаскеля для диапазонов:

[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 интересен. Оператор <* сообщает, что сначала он делает вещь слева, вещь справа второй , но возвращает значение слева. Это позволяет нам получать текущее состояние, увеличивать его, но при этом возвращать полученное значение до было увеличено. Тот факт, что наше представление о состоянии является первоклассным сущностью, и мы можем иметь библиотечные функции, такие как <*, очень мощное. Я нашел эту особую идиому, которая действительно полезна для обхода деревьев, а другие подобные идиомы были весьма полезны для другого кода.

Answer 2

Петли обычно могут быть выражены с использованием различных функций fold. Вот решение, которое использует foldl (вы можете переключиться на foldl', если вы столкнетесь с StackOverflow ошибки):

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], чтобы получить результат для примера из вашего вопроса.

Answer 3

Существует несколько способов решения этой проблемы в зависимости от структуры данных, которую вы хотите использовать. Самый простой из них, вероятно, будет со списками и основных функций, доступных в 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, loop over [0..255], если текущий индекс i удовлетворяет условию, тогда получите текущий idx, напишите его текущему индексу, затем увеличивайте idx. Запустите это как операцию с состоянием, затем заморозите вектор и, наконец, запустите сторону монады ST.Это позволяет спрятать реальный изменчивый вектор в рамках монады ST, чтобы внешний мир не знал, что для вычисления a вам нужно сделать некоторые довольно странные вещи.

Answer 4

Явная рекурсии:

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