haskell - 采用函数式语言的 Kernighan & Ritchie 字数统计示例程序

Question

我最近在网上阅读了一些有关函数式编程的内容，我想我对其背后的概念有了基本的了解。

我很好奇涉及某种状态的日常编程问题是如何用纯函数式编程语言解决的。

例如:《C 编程语言》一书中的字数统计程序如何用纯函数语言实现？

只要解决方案是纯函数式的，我们欢迎任何贡献。

这是书中的字数统计 C 代码:

#include <stdio.h>

#define IN  1 /* inside a word */
#define OUT 0 /* outside a word */

/* count lines, words, and characters in input */
main()
{
  int c, nl, nw, nc, state;

  state = OUT;
  nl = nw = nc = 0;
  while ((c = getchar()) != EOF) {
    ++nc;
    if (c == '\n')
      ++nl;
    if (c == ' ' || c == '\n' || c = '\t')
      state = OUT;
    else if (state == OUT) {
      state = IN;
      ++nw;
    }
  }

  printf("%d %d %d\n", nl, nw, nc);
}

Answer 1

基本上，在函数样式中，您需要根据当前字符和当前状态将获取数据流的 IO 操作与某些有状态转换的纯操作分开。

Tikhon 的 Haskell 解决方案非常干净，但对输入数据执行三遍，并将导致整个输入包含在内存中，直到计算结果。您可以增量处理数据，我在下面使用 Text 包执行此操作，但没有使用其他高级 Haskell 工具(这可能会以牺牲非 Haskell 人员的可理解性为代价来清理数据)。

首先我们有序言:

{-# LANGUAGE BangPatterns #-}

import Data.Text.Lazy as T
import Data.Text.Lazy.IO as TIO

然后我们定义数据结构来保存进程的状态(字符数、单词数和行数以及状态输入/输出):

data Counts = Cnt { nc, nl, nw :: !Int
                  , state :: State  }
        deriving (Eq, Ord, Show)

data State = IN | OUT
        deriving (Eq, Ord, Show)

现在我定义一个“零”状态只是为了方便使用。我通常会创建一些辅助函数或使用像 Lense 这样的包来简单地增加 Counts 结构中的每个字段，但不会给出这个答案:

zeros :: Counts
zeros = Cnt 0 0 0 OUT

现在我将您的一系列 if/else 语句转换为纯状态机:

op :: Counts -> Char -> Counts
op c '\n' = c { nc = nc c + 1, nw = nw c + 1, nl = nl c + 1, state=OUT }
op c ch | ch == ' ' || ch == '\t' = c { nc = nc c + 1, state=OUT }
        | state c == OUT = c { nc = nc c + 1, nw = nw c + 1, state = IN }
        | otherwise  = c { nc = nc c + 1 }

最后，main 函数只获取输入流并将我们的操作折叠到字符上:

main = do
        contents <- TIO.getContents
        print $ T.foldl' op zeros contents

编辑:您提到不理解语法。这是一个更简单的版本，我将对此进行解释:

import Data.Text.Lazy as T
import Data.Text.Lazy.IO as TIO

op (nc, nw, nl, st) ch
  | ch == '\n'              = (nc + 1, nw + 1 , nl + 1, True)
  | ch == ' ' || ch == '\t' = (nc + 1, nw     , nl    , True)
  | st                      = (nc + 1, nw + 1 , nl    , False)
  | otherwise               = (nc + 1, nw     , nl    , st)

main = do
        contents <- TIO.getContents
        print $ T.foldl' op (0,0,0,True) contents

• import 语句使我们能够访问我们使用的 getContents 和 foldl' 函数。

• op 函数使用了一堆守卫 - 像 | 这样的部分ch = '\n' - 基本上类似于 C if/elseif/else 系列。

• 元组( ... , ... , ... , ... ) 包含我们所有的状态。 Haskell 变量是不可变的，因此我们通过向先前变量的值加一(或不加一)来创建新元组。