Point-free Style 思考

Point-free style can (clearly) lead to Obfuscation when used unwisely. As higher-order functions are chained together, it can become harder to mentally infer the types of expressions. The mental cues to an expression’s type (explicit function arguments, and the number of arguments) go missing.

https://wiki.haskell.org/Pointfree

从猫头鹰运算符说起……

The owl ((.)$(.)) has type (a -> b -> c) -> a -> (a1 -> b) -> a1 -> c, and in pointful style can be written as \a b c d -> a b (c d).

Example

> ((.)$(.)) (==) 1 (1+) 0
True

相信大家看到这个抽象东西第一反应是 “什么勾八玩意” 吧！但是其实它还是挺好理解的，只要知道

(.) f g x = f (g x)
($) = id

所以这个运算符其实是 id (.) (.)

也就是 (.) (.) 这个是不是叫奶子运算符

(.) $ (.)
  = (.) (.)
  = λ a b     => (.) (a b)   -- 补充两个被省略的参数
  = λ a b c d => (a b) (c d) -- 补充两个被省略的参数
  = λ a b c d => a b (c d)   -- 消去冗余括号

猫头鹰还有一个进阶版本：

((.).(.))

它也可以用类似的方式推导

((.).(.))
  = λ a       => (.) ((.) a)     -- 补充一个被省略的参数
  = λ a b c   => (.) ((.) a) b c -- 补充两个被省略的参数
  = λ a b c   => ((.) a) (b c)   -- 一次消去
  = λ a b c   => (.) a (b c)     -- 冗余括号消去
  = λ a b c d => (.) a (b c) d   -- 再补个参数
  = λ a b c d => a ((b c) d)     -- 消去
  = λ a b c d => a (b c d)       -- 消去冗余括号

喂喂你 Pointless 了！

Point-free 当然不全是这样的奇技淫巧 —— 当然这个也称不上多奇技淫巧，简单的 β-规约 而已

Point-free 虽然看上去眼花缭乱，但是它其实是培养你对于函数是一等公民，以及函数是一个整体，并且是一个可以用于构建更复杂函数的基本单位的这样一种认知。这在组合子里面非常有用。

当然大家还是一般不会用 (.).(.) 这么抽象的东西的……这样写就真的 Pointless 了

当你写下

sum' xs = foldr (+) 0 xs

的时候，应该能很容易意识到

sum = foldr (+) 0

这件事，因为 foldr (+) 0 实际上组合出了 sum 的逻辑。而一个熟练的函数式写手，应该对后者更熟悉而不是前者。

拿 Parser Combinator 举例子，我在学习在 Lean4 中使用 Parser Combinator 中很自然而然地写下了 pointfree 的逻辑，因为只要你把 parser 的函数看成可以组合的积木，而不需要关心它的实际参数来源的话，pointfree 写法就是最自然的：

mutual
  partial def parseArray : Parser Json := do
    _ ← char '['
    _ ← whitespaces
    let elems ← sepBy parseJson (char ',')
    _ ← whitespaces
    _ ← char ']'
    return Json.arr elems

  partial def parseObject : Parser Json := do
    _ ← char '{'
    _ ← whitespaces
    let pairs ← sepBy parsePair (char ',')
    _ ← whitespaces
    _ ← char '}'
    return Json.obj pairs

  partial def parsePair : Parser (String × Json) := do
    _ ← whitespaces
    let key ← quotedString
    _ ← whitespaces
    _ ← char ':'
    let value ← parseJson
    return (key.asString, value)

  partial def parseJson : Parser Json := do
    let _ ← whitespaces
    let json ← fun str => match str with
      | 'n' :: _ => parseNull str
      | 't' :: _ => parseTrue str
      | 'f' :: _ => parseFalse str
      | '[' :: _ => parseArray str
      | '{' :: _ => parseObject str
      | '"' :: _ => parseString str
      | _ => parseNumber str
    let _ ← whitespaces
    return json
end

当然如果你再入味一点，你可能会写出这种 shit：

partial def parseObject : Parser Json :=
  Json.obj <$> (
    char '{' *> whitespaces *> (
      sepBy parsePair (char ',')
    ) <* whitespaces <* char '}'
  )

相比之下，同为函数式语言，由于没有很好的 currying，Gleam 重构上述代码写出来的解析器就凌乱不堪：

fn object_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, input) <- result.then(char("{")(input))
    let input = input |> string.trim
    use #(val, input) <- result.then(seq_by(
      pair_parser(),
      char(",") |> chain(whitespace()),
    )(input))
    let input = input |> string.trim
    use #(_, input) <- result.then(char("}")(input))
    Ok(#(Obj(dict.from_list(val)), input))
  }
}
完整代码 
import gleam/dict
import gleam/io
import gleam/list
import gleam/result
import gleam/string

pub type Node {
  Nul
  Bol(val: Bool)
  Num(val: Int)
  Str(val: String)
  Arr(val: List(Node))
  Obj(val: dict.Dict(String, Node))
}

type Parser(t) =
  fn(String) -> Result(#(t, String), String)

fn or(p1: Parser(a), p2: Parser(a)) -> Parser(a) {
  fn(input: String) {
    case p1(input) {
      Ok(x) -> Ok(x)
      Error(_) -> p2(input)
    }
  }
}

fn chain(p1: Parser(a), p2: Parser(b)) -> Parser(#(a, b)) {
  fn(input: String) {
    use #(res1, input) <- result.then(p1(input))
    use #(res2, input) <- result.then(p2(input))
    Ok(#(#(res1, res2), input))
  }
}

fn char(c: String) -> Parser(String) {
  fn(str: String) {
    case str |> string.pop_grapheme {
      Error(Nil) -> Error("Unexpected EOF")
      Ok(#(first, rest)) if first == c -> Ok(#(first, rest))
      Ok(_) -> Error("unexpected token " <> str)
    }
  }
}

fn whitespace() -> Parser(#()) {
  fn(input: String) { Ok(#(#(), input |> string.trim)) }
}

fn ident(id: String) -> Parser(String) {
  fn(str: String) {
    case str |> string.starts_with(id) {
      True -> Ok(#(id, str |> string.drop_start(string.length(id))))
      False -> Error("unexpected token " <> str)
    }
  }
}

fn true_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, rest) <- result.then(ident("true")(input))
    Ok(#(Bol(val: True), rest))
  }
}

fn false_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, rest) <- result.then(ident("false")(input))
    Ok(#(Bol(val: False), rest))
  }
}

fn null_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, rest) <- result.then(ident("null")(input))
    Ok(#(Nul, rest))
  }
}

fn string_key_parser() -> Parser(String) {
  fn(input: String) {
    use #(_, rest) <- result.then(char("\"")(input))
    case rest |> string.split_once("\"") {
      Ok(#(val, rest)) -> Ok(#(val, rest))
      Error(_) -> Error("unexpected token " <> input)
    }
  }
}

fn string_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, rest) <- result.then(char("\"")(input))
    case rest |> string.split_once("\"") {
      Ok(#(val, rest)) -> Ok(#(Str(val: val), rest))
      Error(_) -> Error("unexpected token " <> input)
    }
  }
}

fn go_for_seq_by(
  p: Parser(a),
  sep: Parser(b),
  acc: List(a),
  input: String,
) -> #(List(a), String) {
  case p(input) {
    Ok(#(val, rest)) ->
      case sep(rest) {
        Ok(#(_, rest)) -> go_for_seq_by(p, sep, acc |> list.append([val]), rest)
        Error(_) -> #(acc |> list.append([val]), rest)
      }
    Error(_) -> #(acc, input)
  }
}

fn seq_by(p: Parser(a), sep: Parser(b)) -> Parser(List(a)) {
  fn(input: String) { Ok(go_for_seq_by(p, sep, [], input)) }
}

fn array_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, input) <- result.then(char("[")(input))
    let input = input |> string.trim
    use #(val, input) <- result.then(seq_by(
      json_parser(),
      char(",") |> chain(whitespace()),
    )(input))
    let input = input |> string.trim
    use #(_, input) <- result.then(char("]")(input))
    Ok(#(Arr(val), input))
  }
}

fn pair_parser() -> Parser(#(String, Node)) {
  fn(input: String) {
    let input = input |> string.trim
    use #(key, input) <- result.then(string_key_parser()(input))
    let input = input |> string.trim
    use #(_, input) <- result.then(char(":")(input))
    let input = input |> string.trim
    use #(val, input) <- result.then(json_parser()(input))
    let input = input |> string.trim
    Ok(#(#(key, val), input))
  }
}

fn object_parser() -> Parser(Node) {
  fn(input: String) {
    use #(_, input) <- result.then(char("{")(input))
    let input = input |> string.trim
    use #(val, input) <- result.then(seq_by(
      pair_parser(),
      char(",") |> chain(whitespace()),
    )(input))
    let input = input |> string.trim
    use #(_, input) <- result.then(char("}")(input))
    Ok(#(Obj(dict.from_list(val)), input))
  }
}

fn json_parser() -> Parser(Node) {
  fn(input: String) {
    case input |> string.trim {
      "t" <> _ -> true_parser()(input)
      "f" <> _ -> false_parser()(input)
      "n" <> _ -> null_parser()(input)
      "\"" <> _ -> string_parser()(input)
      "[" <> _ -> array_parser()(input)
      "{" <> _ -> object_parser()(input)
      x -> Error("unexpected token " <> x)
    }
  }
}

fn parse_json(input: String) -> Result(Node, String) {
  case json_parser()(input |> string.trim) {
    Ok(#(node, rest)) -> {
      case rest {
        "" -> Ok(node)
        _ -> Error("unexpected token " <> rest)
      }
    }
    Error(err) -> Error(err)
  }
}

pub fn main() {
  let _ = io.debug(parse_json("null"))
  let _ = io.debug(parse_json("true"))
  let _ = io.debug(parse_json("false"))
  let _ = io.debug(parse_json("\"wwww\""))
  let _ = io.debug(parse_json("{}"))
  let _ = io.debug(parse_json("{\"a\": true, \"b\": [true, false, null]}"))
  let _ = io.debug(parse_json("[ true, false, null, \"abcd\" ]"))

  io.debug("done")
}

为什么 Gleam 这样写就凌乱不堪？因为核心观念，即函数可以自由地组合，在这里没有得到很好的体现。还是以一种描述过程的写法去写函数式，自然会如此。

Functional Haskell Code