将一段需要使用命令式for循环的代码转换为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;

该算法基本上为直方图的映射函数创建了一个查找表。

您知道哪些资源可以帮助我更好地理解这种问题吗？

- fuji

Answer 1

在函数式编程中的一个核心思想是将算法表达为数据转换。在像Haskell这样的惰性语言中，我们甚至可以更进一步地将惰性数据结构视为具体化的计算。从非常实际的意义上讲，Haskell的列表更像循环而不是普通的链接列表：它们可以逐步计算，不必一次性存在于内存中。同时，我们仍然可以获得许多类似数据类型的优点，例如能够传递和使用模式匹配进行检查。

有了这个想法，“技巧”就是用索引来表示for循环，需要创建所有可能取值的列表。您的示例可能是最简单的情况：i的取值范围为0到255，因此我们可以使用Haskell的内置范围表示法。

[0..255]

在高层次上，这是Haskell中的等效于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类型方面具有自己的函数。核心抽象稍微复杂一些（请阅读[“你本来可以发明单子”][you]以获得很好的介绍），但最终代码实际上非常易于阅读（我想除了导入外: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函数的第一个情况很有趣。 <*运算符告诉它首先执行左侧的操作，然后执行右侧的操作，但返回左侧的值。这使我们可以获得当前状态，增加它，但仍然返回在递增之前获得的值。我们的状态概念是一个一等公民，我们可以拥有像<*这样的库函数，这非常强大-我发现这种特定的习惯用法对于遍历树非常有用，其他类似的习惯用法对于其他代码也非常有用。

- Tikhon Jelvis

---

非常好的回答。在这之前我不知道状态单子。非常感谢！ - fuji

Answer 2

根据您想要使用的数据结构，有几种方法可以解决这个问题。最简单的方法可能是使用列表和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

这里使用了两个累加器的worker模式，idx和out，并且遍历最后一个参数，直到没有元素为止，然后返回out。虽然这可以转换为某种类型的fold，但无论如何，使用++附加项目到列表中非常低效。您可以通过使用idx : out和0: out，然后在go输出上使用reverse来改进它，但它仍然不是一个理想的解决方案。

另一种解决方案可能是使用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

这个代码显然更加紧急。在flip runState 1中，1表示你的初始状态是idx = 1 ，然后使用 forM(看起来像是一个for循环，但实际上不是) 遍历 [0..255], 循环变量是i，然后只需要实现其余的逻辑即可。

如果你想要更高级的操作，可以使用StateT和ST monad同时拥有实际的可变数组和状态。关于如何实现这一点的解释超出了本回答的范围。

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需要做一些相当奇怪的事情。

- bheklilr

Answer 3

显式递归：

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

- chi

Answer 4

循环通常可以使用不同的fold函数表示。这里是一个解决方案，它使用foldl(如果遇到stackoverflow错误，您可以切换到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]来获得您问题示例的结果。

- kraskevich