8

我在将命令式算法转换为函数式风格时遇到了一些困难。我无法理解的主要概念是如何根据序列在序列中的位置用值填充序列。在 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

4 回答 4

8

函数式编程的核心思想之一是将算法表示为数据转换。在像 Haskell 这样的惰性语言中，我们甚至可以更进一步，将惰性数据结构视为具体计算。在非常真实的意义上，Haskell 的列表比普通的链表更像循环：它们可以增量计算，不必一次全部存在于内存中。同时，我们仍然获得了具有传递它并使用模式匹配检查它的能力的数据类型的许多优点。

考虑到这一点，用索引表示 for 循环的“技巧”是创建一个它可以采用的所有值的列表。您的示例可能是最简单的情况：从toi获取所有值，因此我们可以使用 Haskell 的内置表示法来表示范围：0255

[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 could Have Invented Monads"][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函数的第一种情况很有趣。<*运算符告诉它先做左边的事情，然后做右边的事情，但返回左边的值。这让我们可以获取当前状态，增加它，但仍然返回我们在增加之前获得的值。我们的状态概念是一流的实体，我们可以拥有类似<*的库函数这一事实非常强大——我发现这个特殊的习惯用法对于遍历树非常有用，并且其他类似的习惯用法对于其他代码也非常有用。

于 2015-03-27T18:25:21.443 回答
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您可以通过使用and使其变得更好0 : out，然后reverse在 的输出上使用go，但这仍然不是一个理想的解决方案。

另一种解决方案可能是使用Statemonad：

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

这当然看起来更有必要。1inflip runState 1表示您的初始状态是，idx = 1然后您使用forM（看起来像 for 循环但实际上不是） over [0..255]，循环变量是i，然后只需实现其余逻辑即可。

如果你想更高级，你可以使用StateT和STmonads 来同时拥有一个实际的可变数组和一个状态。但是，对其工作原理的解释远远超出了此答案的范围：

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。将其作为有状态操作运行，然后冻结向量，最后运行STmonad 方面。这允许一个实际的可变向量安全地隐藏在STmonad 中，这样外界就不知道要计算a你必须做一些相当奇怪的事情。

于 2015-03-27T18:17:30.153 回答
1

显式递归：

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  ))
于 2015-03-27T18:20:04.627 回答
0

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

于 2015-03-27T18:10:27.520 回答