模式匹配和for循环的相似之处

函数式新手经常遇到的一个问题是似乎我不能写for循环了。这篇博客会带你看看不同的for循环对应到函数式是怎么样的。

遍历集合

你们应该都见过这种代码：

for x in xs:
    update_state(state, x)
return state;

这种经常是基于迭代器的，我们把它去糖一下，这里用Java：

for (Foo x: collectionOfFoo)
    do_something_with(state, x);
return state;

// into
var iter = collectionOfFoo.iterator();
while (iter.hasNext()) {
    var x = iter.peek();
    do_something_with(state, x);
    iter.next();
}
return state;

没那么好看了吧！

注意到每次循环我们都在更新状态，每次循环迭代器要么为空要么有下一个值，在循环里面我们会“解构”迭代器（把头拔下来）直到它变成空的为止。我们在Haskell里也能干一模一样的事：

-- 空的情况
traverse_collection []     state     = state

-- 执行循环逻辑并“进入下一次循环”
traverse_collection iter state       = traverse_collection (tail iter) (do_something_with state (head iter))

-- 而用模式匹配：
-- traverse_collection (x:xs) state  = traverse_collection xs (do_something_with state x)

注意到do_something_with 一直在那，但进入下一次循环的逻辑隐含在递归里。

Haskell版里用的模式匹配还包含了“把头拔下来”，因为大部分Haskell的数据结构都是递归的。在Java版里没写这个逻辑，写了会更长。

这一整套逻辑被抽象成了foldl，Java增强形for循环要求你是Iterable，同理，foldl要求Foldable。

执行某逻辑X次

接下来我们再看看“执行某逻辑X次”的循环，这种一般函数式新手最怀念（可能是因为他们之前学到所有循环都基于这一种），不过接下来我们会发现命令式地写这种逻辑很啰嗦而且没有糖。

int fib(int n) {
    int x = 1;
    int y = 1;
    for (int i = 0; i < n - 1; i++) {
        int tmp = y;
        y += x;
        x = tmp;
    }
    return y;
}

而在函数式的版本中我们可以用尾递归实现一模一样的逻辑，而且还短很多。

fib n = fib' 0 1 n
    where
        fib' _ y 0 = y
        fib' x y n' = fib' y (x + y) (n' - 1)

带下标地遍历集合

for (int i = 0; i < xs.length; i++)
    do_something_with(i, xs[i], state)

在Haskell版中我们可以复用之前的traverse_collection。

-- 定义新的需要下标的do_something_with

f xs state = traverse_collection (zip xs [1..]) state

注意到命令式的脱糖后需要更多的代码，但函数式的代码量没有增多（当然这里用foldl更方便）。

你可以用stream API来获得相似的体验，但他自己就是借鉴自函数式的 😃

例：根据空格分割字符串

Java:

List<String> split(String input) {
    var state = new ArrayList<String>();
    state.add("");
    for (char c: input.toCharArray()) {
        if (c == ' ') {
            state.add("");
        } else {
            var index = state.size() - 1;
            state.set(index, state.get(index) + c);
        }
    }
    return state;
}

// split("Hello Functional Programming");
// ==> [Hello, Functional, Programming]

Haskell:

split :: String -> [String]
split str = reverse (split' str [""])
    where
        split' :: String -> [String] -> [String]
        split' [] ss = ss
        split' (x:xs) ss@(h:t)
            | x == ' ' = split' xs ("" : ss)
            | otherwise = split' xs ((h ++ [x]):t)

-- λ ->  split "Hello Functional Programming"
-- ["Hello", "Functional", "Programming"]

不用reverse百分百对应java逻辑的版本

split :: String -> [String]
split str = split' str [""]
    where
        split' :: String -> [String] -> [String]
        split' [] ss = ss
        split' (x:xs) ss
            | x == ' ' = split' xs (ss `snoc` "")
            | otherwise = split' xs (changeLast ss (last ss `snoc` x))

        -- 这两个都是标准库里的，不过我放在这以便查看
        snoc xs x = xs ++ [x]
        changeLast xs x = init xs ++ [x]

-- λ ->  split "Hello Functional Programming"
-- ["Hello", "Functional", "Programming"]