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工具(可以通过非Haskellers来理解可清除性).

首先我们有序言:

{-# LANGUAGE BangPatterns #-}

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

然后我们定义我们的数据结构来保存进程的状态(字符,单词和行的数量以及状态IN/OUT):

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变量是不可变的,因此我们通过在先前变量的值中添加一个(或不添加)来创建新元组.

Answer 2

一种简单的方法是读入输入,然后使用一些简单的函数来获取行/字/字符数.像这样的东西会起作用:

count :: String -> (Int, Int, Int)
count str = (length $ lines str, length $ words str, length str)

main :: IO ()
main = fmap count getContents >>= print

这不完全一样,但它很接近.

这非常简单.给定一个字符串,我们可以将其转换为带有标准lines函数的行列表和带有标准函数的单词列表words.既然String只是[Char],length返回字符数.这就是我们如何获得三项计数.(供参考,length $ lines str与之相同length (lines str).)

重要的想法是如何 - IO读取输入并将其打印出来 - 与实际逻辑分离.

此外,我们不是通过字符跟踪某个状态来输入字符,而是通过将简单函数应用于输入来获得实际数字.这些函数都只是标准库函数的组合.

Answer 3

在你的循环中有四个状态变量,nc,nw,nl和state,加上下一个字符c.循环记住从最后一次循环开始的nc,nw,nl和state,并且c通过循环改变每次迭代.想象一下,你将这些变量从循环中取出并将它们放在一个向量中:[state,nc,nw,nl].然后将循环结构更改为带有两个参数的函数,第一个是向量[state,nc,nw,nl],第二个是c,并返回一个新的向量,其更新值为nc,nw,nl和州.在C-ish伪代码中:

f([state, nc, nw, nl], c) {
    ++nc;
    if (c == '\n')
      ++nl;
    if (c == ' ' || c == '\n' || c = '\t')
      state = OUT;
    else if (state == OUT) {
      state = IN;
      ++nw;
    }
    return [state, nc, nw, nl];
}

现在你可以用向量[OUT,0,0,0]和字符串中的第一个字符("你好,世界",比如说)调用该函数,它将返回一个新的向量[IN,1,0,0 ].使用这个新向量和第二个字符'e'再次调用f,它返回[IN,2,0,0].对字符串中的其余字符重复此操作,最后一次调用将返回[IN,12,2,0],与C代码打印的值相同.基本思想是将状态变量从循环中取出,将循环的内容转换为函数,并将状态变量的向量和下一个输入作为参数传递给该函数,并返回一个新的状态向量作为结果.有一个名为reduce的函数可以做到这一点.

以下是如何在Clojure中执行此操作(格式化以强调返回的向量):

(defn f [[state nc nw nl] c]
  (let [nl (if (= c \n)(inc nl) nl)]
    (cond
     (or (= c \space)(= c \n)(= c \t)) [:out  (inc nc) nw       nl]
     (= state :out)                    [:in   (inc nc) (inc nw) nl]
     true                              [state (inc nc) nw       nl]
)))

(defn wc [s] (reduce f [:out 0 0 0] s))

(wc "hello, world")

返回(并在repl中打印)[:in 12 2 0]

Answer 4

这是我在Scheme中使用纯函数,严格,单通道,尾递归解决方案的镜头:

(define (word-count input-port)
  (let loop ((c (read-char input-port))
             (nl 0)
             (nw 0)
             (nc 0)
             (state 'out))
    (cond ((eof-object? c)
           (printf "nl: ~s, nw: ~s, nc: ~s\n" nl nw nc))
          ((char=? c #\newline)
           (loop (read-char input-port) (add1 nl) nw (add1 nc) 'out))
          ((char-whitespace? c)
           (loop (read-char input-port) nl nw (add1 nc) 'out))
          ((eq? state 'out)
           (loop (read-char input-port) nl (add1 nw) (add1 nc) 'in))
          (else
           (loop (read-char input-port) nl nw (add1 nc) state)))))

word-count接收input port一个参数; 请注意,不会创建其他数据结构(结构,元组,向量等),而是将所有状态保存在参数中.例如,对于包含以下内容的文件中的单词计数:

hello, world

调用这样的过程:

(call-with-input-file "/path/to/file" word-count)
> nl: 0, nw: 2, nc: 12