将命令式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;

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

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

Answer 1

函数式编程的核心思想之一是将算法表达为数据转换.在像Haskell这样的惰性语言中,我们甚至可以更进一步,将惰性数据结构视为具体计算.在一个非常真实的意义上,Haskell的列表更像是循环而不是普通的链表:它们可以递增计算,而不必一次存在于内存中.与此同时,我们仍然可以获得许多优势,即拥有类似于传递数据类型的数据类型并使用模式匹配进行检查.

考虑到这一点,表达带索引的for循环的"技巧"是创建它可以采用的所有值的列表.你的例子可能是最简单的情况:i从接受全部的值0来255,所以我们可以使用Haskell的内置的符号来表示范围:

[0..255]

在较高的层面上,这是Haskell的等价物for (i = 0 to 255); 然后,我们可以通过递归函数或标准库中的高阶函数遍历此列表来执行循环中的实际逻辑.(第二种选择是首选.)

这个特殊的逻辑非常适合a 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类型方面具有其自己的功能.核心抽象有点复杂(通过["你可以发明Monad"] [你]阅读一篇很好的介绍),但结果代码实际上非常令人愉快(除了导入,我猜: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函数的第一个案例很有趣.该<*运营商告诉它做的事左边第一个,这件事,右边第二,但在左侧返回值.这让我们得到当前状态,增加它但仍然返回我们在增加之前得到的值.事实上,我们的状态概念是一流的实体,我们可以拥有类似的库函数<*非常强大 - 我发现这个特定的习惯用法非常适合遍历树,而其他类似的习语对其他代码非常有用.