一道数字解析面试题的函数式解法
以下是leetcode上一道标注为"困难"的题：
验证给定的字符串是否可以解释为十进制数字。
例如:
"0" => true
" 0.1 " => true
"abc" => false
"1 a" => false
"2e10" => true
" -90e3 " => true
" 1e" => false
"e3" => false
" 6e-1" => true
" 99e2.5 " => false
"53.5e93" => true
" --6 " => false
"-+3" => false
"95a54e53" => false
不同于算法题，它的难点不在于如何提高执行效率，缩减执行时间，而在于如何清晰、正确地完成"复杂"业务逻辑到代码的转换。参考题解大多使用了显式维护状态机的思路，通过仔细构建状态转移表，再将状态转移表用代码进行表述，能得到执行效率颇高(O(n))的算法。不过这种解法对代码复用很不友好，稍微改下题目，例如"验证给定字符串是否可以解释为复数"，就得重新构建状态转移表，重新写代码。而且构建状态转移表的过程是机械化、串行的，与人类通过层层分解来处理复杂问题的习惯相悖，这就导致对大部分人而言，构建状态转移表枯燥而容易出错。
本文受haskell中的parsec库启发，尝试基于java8引入的函数式特性(lambda和method reference)，先实现一个简陋的java版parsec，然后使用这个库定义一组number parser，用来解决文章开头提到的面试题。
预览
简而言之，我们最终将得到一组parser库，在这个库的基础上，可以使用声明式语法构建具体的文本解析器。最终用来解析leetcode 面试题的parser可以按如下方式构建：
// 无符号整数
public static final Parser<Int> unsignedInt = digits1plus.map(Int::unsigned);
// 有符号整数
public static final Parser<Int> signedInt = seq(flag, unsignedInt, Int::signed);
// 包含整数部分的无符号浮点数
public static final Parser<Float> fullUnsignedFloat =
seq(digits1plus, point.then(digits0plus), Float::full);
// 不含整数部分的无符号浮点数
public static final Parser<Float> onlyFractionPartUnsignedFloat =
point.then(digits1plus).map(Float::onlyFractionPart);
// 只含整数部分的无符号浮点数
public static final Parser<Float> onlyIntPartUnsignedFloat =
digits1plus.map(Float::onlyIntPart);
// 任意无符号浮点数
public static final Parser<Float> unsignedFloat =
fullUnsignedFloat.or(onlyFractionPartUnsignedFloat).or(onlyIntPartUnsignedFloat);
// 任意有符号浮点数
public static final Parser<Float> floatParser = seq(flag, unsignedFloat, Float::signed);
// 包含指数部分的科学计数
public static final Parser<Number> withExpNumber = seq(floatParser, expFlag.then(signedInt),
Number::full);
// 不包含指数部分的科学计数
public static final Parser<Number> justFloatNumber = floatParser.map(Number::justFloat);
// 任意科学计数
public static final Parser<Number> number = withExpNumber.or(justFloatNumber);
// 前后为空白的任意科学计数, 用于解决leetcode面试题
public static final Parser<Number> numberSurroundWithSpaces = number.surroundWith(spaces);
怎么实现？
我们将使用函数式编程的思想，构建一个简易的适合组合的parser库。关于函数式编程，在scala with cats一书中有一个简单而明确的解释：
This means designing systems as small composable units, expressing constraints and interactions via the type system, and using composition to guide the construction of large systems in a way that maintains the original architectural vision.
这个过程有点像拼积木，使用简单的基本构件，通过层层组合，构造出更大更复杂的系统：
定义关键类型
函数式编程的要素之一是无副作用的”纯“函数（pure function）。和数学函数一样，这类函数的返回值，完全由调用者提供的参数决定，而且除了返回结果外，不执行其他任何带副作用的操作。相对的，”不纯“的函数，它的返回值可能依赖当前时间这类定义不明确而且易变的状态，可能执行一些副作用（side effect），例如抛出异常、修改全局状态等。
定义出纯函数的关键，在于明确输入输出的类型，做到不偏不倚，让输入包含函数执行所需的全部信息，让输出体现全部可能的结果。
对于一个parser来说，输入比较简单，就是一个字符串流：
interface CharStream {
/**
* 是否有更多字符等待解析
*/
boolean hasMore();
/**
* 读取第一个字符(如果有的话)
*/
char peek();
/**
* 在当前字符流中前进一步
*/
CharStream advance();
}
输出则复杂一点，parse可能失败，也可能成功，parse之后，字符流可能被消费了若干个字符。这些都应该通过类型体现出来：
class ParseResult<T> {
private final Throwable error;
private final T value;
private final CharStream stream;
ParseResult(Throwable error, T value, CharStream stream) {
this.error = error;
this.value = value;
this.stream = stream;
}
public static <T> ParseResult<T> success(T value, CharStream stream) {
Objects.requireNonNull(stream);
return new ParseResult<>(null, value, stream);
}
public static <T> ParseResult<T> error(Throwable error, CharStream stream) {
Objects.requireNonNull(stream);
return new ParseResult<>(error, null, stream);
}
}
这里用了泛型来描述parse后得到的值，以表示可以从字符流中解析得到各种结构化数据，而不只是题目中提到的数字。值得注意的是，ParserResult中error和value其实是互斥的，两者必定一个为null，一个为非null，不过java的类型系统不能优雅地描述这种类型限定(sum type)，需要我们在运行时做一些检查以保证这种约束关系的成立。另外，为了方便地基于ParseResult进行更进一步的运算，我们可以使用类成员函数的方式定义一些read类方法：
public Throwable getError() {
return error;
}
public T getValue() {
return value;
}
public CharStream getStream() {
return stream;
}
public <T1> ParseResult<T1> valueMap(Function<T, T1> mapper) {
if (isFailed()) {
@SuppressWarnings("unchecked")
ParseResult<T1> valueMappedParseResult = (ParseResult<T1>) this;
return valueMappedParseResult;
} else {
return success(mapper.apply(value), stream);
}
}
public ParseResult<T> onError(Consumer<Throwable> consumer) {
if (isFailed()) {
consumer.accept(error);
}
return this;
}
public ParseResult<T> onValue(Consumer<T> consumer) {
if (isSucceed()) {
consumer.accept(value);
}
return this;
}
其中valueMap和java 8中的Optional.map类似，parse result为fail的话，则什么都不做直接返回fail result，否则的话，将parse得到的value进行进一步转换。这类方法的共同点在于，用”高阶函数“将重复出现的pattern（这里的pattern是传播错误，转换结果）抽象成类型安全的API，优点是方便对其他函数进行组合和减少重复代码。
定义好输入输出类型后，parser的类型也就确定了：
interface Parser<T> {
ParseResult<T> parse(CharStream stream);
}
这种只含一个抽象方法的interface在java 8中叫做functional interface。它既可以由普通class实现，也可以由method reference和lambda 表达式实现。正是这一特性，让我们可以在java这种函数并非一等公民的语言中，比较优雅地实现函数式编程。
处理parser之间的组合
函数式编程的要素之二，是能够对函数方便、安全地进行组合，这样我们才能像搭积木一样，从简单、坚实的基础组件出发，构建更大、更复杂、功能更丰富的系统，同时保证这个大的系统和基础组件一样坚实、稳定。
而要实现对函数方便、安全地进行组合，关键在于定义和前面提到的valueMap类似的高阶函数。要定义合理的高阶函数，则首先需要识别出计算中重复出现的pattern，然后将这些pattern进行抽象。
例如，定义parser时，可能遇到的pattern包括：
- 使用parser<T>得到T类型的结果，然后判断结果是否符合某种特征，不符合的话，就返回解析失败
default Parser<T> filter(Predicate<T> predicate) {
return stream -> {
ParseResult<T> result = parse(stream);
if (result.isFailed()) {
return ParseResult.error(result.getError(), stream);
} else {
T value = result.getValue();
if (predicate.test(value)) {
return result;
} else {
return ParseResult.error(
new Throwable(String.format("%s not match against predicate", value)), stream);
}
}
};
}
- 使用parser<T>得到T类型的结果，然后再将T类型的结果转换成类型为T1的值
default <T1> Parser<T1> map(Function<T, T1> mapper) {
return stream -> parse(stream).valueMap(mapper);
}
- 先使用parser 1解析，成功的话直接返回结果，失败了再使用parser 2解析
default Parser<T> or(Parser<T> recoverParser) {
return stream -> {
ParseResult<T> result = parse(stream);
if (result.isFailed()) {
return recoverParser.parse(stream);
} else {
return result;
}
};
}
- 使用parser<T>得到T类型的结果，然后基于结果t决定如何解析字符流的其余部分
default <T1> Parser<T1> flatMap(Function<T, Parser<T1>> mapper) {
return stream -> {
ParseResult<T> result = parse(stream);
if (result.isFailed()) {
return (ParseResult<T1>) result;
} else {
Parser<T1> nextParser = mapper.apply(result.getValue());
return nextParser.parse(result.getStream());
}
};
}
- 使用parser<T>得到T类型的结果，失败的话，返回解析失败；成功的话，用parser<T1>解析剩余的字符流，但是T结果弃之不用。
default <T1> Parser<T1> then(Parser<T1> parser) {
return stream -> {
ParseResult<T> result = parse(stream);
if (result.isFailed()) {
return (ParseResult<T1>) result;
} else {
return parser.parse(result.getStream());
}
};
}
- 使用parser<T1>得到T类型的结果，成功的话，继续使用parser<T2>解析剩余的字节流，最后基于结果T1和T2构建最终结果T3
static <T1, T2, T3> Parser<T3> seq(Parser<T1> parser1, Parser<T2> parser2,
BiFunction<T1, T2, T3> merger) {
return parser1.flatMap(t1 -> parser2.map(t2 -> merger.apply(t1, t2)));
}
这个定义基本上只是flatMap和map的一个封装，其实并没有引入更深一层的抽象。之所以组这个封装，是为了避免实际应用中出现嵌套lambda，影响代码可读性。理论上，当然还可以定义seq3，seq4，seq5等封装。而在Haskell等函数式语言中，则通过do..return语法糖来解决这一问题。
- 重复使用parser<T>进行解析，然后将结果收集到一个list中。list长度和parse成功的次数相同。
static <T> Parser<List<T>> more(Parser<T> subParser) {
return stream -> {
List<T> results = new ArrayList<>();
ParseResult<T> result = subParser.parse(stream);
while (result.isSucceed()) {
results.add(result.getValue());
stream = result.getStream();
result = subParser.parse(stream);
}
return ParseResult.success(results, stream);
};
}
- 和7类似，但是要求必须至少parse成功一次
static <T> Parser<List<T>> more1(Parser<T> subParser) {
return more(subParser).filter(list -> !list.isEmpty());
}
这里不再罗列所有组合函数，完整代码见这个gist。
为数字解析定义值类型
为了完成接下来的数字解析器，我们先自定义一些数据类型，用来更清晰地表示各种数字的组成。
例如，一组数字字符可以通过如下class表示：
class Digits {
static final Digits empty = new Digits(Collections.emptyList());
final List<Character> digits;
Digits(List<Character> digits) {
this.digits = digits;
}
@Override
public String toString() {
return digits.stream().map(String::valueOf).collect(Collectors.joining());
}
public boolean isEmpty() {
return digits.isEmpty();
}
}
一个整数，由一个符号位，和一组数字字符组成：
class Int {
static final Int empty = unsigned(Digits.empty);
final Character flag;
final Digits digits;
public Int(Character flag, Digits digits) {
this.flag = flag;
this.digits = digits;
}
static Int unsigned(Digits digits) {
return new Int(null, digits);
}
static Int signed(Character flag, Int unsigned) {
return new Int(flag, unsigned.digits);
}
@Override
public String toString() {
return flag == null ? digits.toString() : flag + digits.toString();
}
public boolean isEmpty() {
return digits.isEmpty();
}
}
一个形如-3.14156的浮点数，可以认为由三部分组成-符号位，小数点前的整数部分，小数点后的部分：
class Float {
final Character flag;
final Digits intPart;
final Digits fractionPart;
public Float(Character flag, Digits intPart, Digits fractionPart) {
this.flag = flag;
this.intPart = intPart;
this.fractionPart = fractionPart;
}
static Float full(Digits intPart, Digits fractionPart) {
assert !intPart.isEmpty();
assert !fractionPart.isEmpty();
return new Float(null, intPart, fractionPart);
}
static Float onlyIntPart(Digits intPart) {
assert !intPart.isEmpty();
return new Float(null, intPart, Digits.empty);
}
static Float onlyFractionPart(Digits fractionPart) {
return new Float(null, Digits.empty, fractionPart);
}
static Float signed(Character flag, Float unsigned) {
return new Float(flag, unsigned.intPart, unsigned.fractionPart);
}
@Override
public String toString() {
String formattedUnsignedPart = String.format("%s.%s", intPart, fractionPart);
return flag == null ? formattedUnsignedPart : flag + formattedUnsignedPart;
}
public boolean isEmpty() {
return intPart.isEmpty() && fractionPart.isEmpty();
}
}
而一个形如-3.1415E10的科学计数，则可以认为由两个部分组成-浮点数部分，以及E后面的指数部分：
class Number {
final Float floatPart;
final Int expPart;
Number(Float floatPart, Int expPart) {
this.floatPart = floatPart;
this.expPart = expPart;
}
static Number full(Float floatPart, Int expPart) {
assert !floatPart.isEmpty();
assert !expPart.isEmpty();
return new Number(floatPart, expPart);
}
static Number justFloat(Float floatPart) {
assert !floatPart.isEmpty();
return new Number(floatPart, Int.empty);
}
@Override
public String toString() {
StringBuilder stringBuilder = new StringBuilder();
stringBuilder.append(floatPart);
if (expPart != null) {
stringBuilder.append('e').append(expPart);
}
return stringBuilder.toString();
}
}
注意，Int、Float、Number等自定义类型，主要是用来定义相关数据的字面构成，而不没有包含任何数值运算的部分。当然，要用这些class的实例做数值计算也简单，给每个class都实现一个到double或long的转换函数就好。
到这里，一个简易的parser combinator library就算搭建完成了。接下来，我们可以转移到”应用层“-构建数字解析器。
构建常见的基础parser
前面提到，函数式编程类似于搭积木。我们已经花了很大篇幅来定义积木之间组合的规则，这一步我们开始制作几个基础积木，也就是无法基于其他parser组合得到的基础parser。
- 提取任意单个字符的parser
public static final Parser<Character> one = stream -> {
if (!stream.hasMore()) {
return ParseResult.error(new Throwable("no more characters"), stream);
} else {
return ParseResult.success(stream.peek(), stream.advance());
}
};
- 匹配空字符流/字符流末尾的parser
public static Parser<Void> eof = stream -> {
if (stream.hasMore()) {
return ParseResult.error(new Throwable("there are more characters"), stream);
} else {
return ParseResult.success(null, stream);
}
};
组合
有了前面提到的两个基础parser，以及前面的组合规则，我们可以开始逐步构造一些”更实用“的简单parser了。例如：
- 单个数字/多个数字
public static Parser<Character> digit = one.filter(ch -> ch >= '0' && ch <= '9');
public static final Parser<Digits> digits0plus = more(digit).map(Digits::new);
public static final Parser<Digits> digits1plus = more1(digit).map(Digits::new);
- 单个空格/多个空格
public static Parser<Character> space = one.filter(eq(' '));
public static Parser<List<Character>> spaces = more(space);
- 正负符号
public static final Parser<Character> positiveFlag = one.filter(eq('+'));
public static final Parser<Character> negativeFlag = one.filter(eq('-'));
public static final Parser<Character> flag = positiveFlag.or(negativeFlag).or(just(null));
- 小数点
public static final Parser<Character> point = one.filter(eq('.'));
- e指数符号
public static final Parser<Character> expFlag = one.filter(ch -> ch == 'e' || ch == 'E');
再组合
有了数字，正负符号，小数点，我们就可以逐步开始构建无符号整数->整数->浮点数->科学计数啦：
无符号整数的语法很简单，一到多个数字字符连续排列即可：
public static final Parser<Int> unsignedInt = digits1plus.map(Int::unsigned);
如果你想严格一点，要求第一个字符不能为0的话，改动也比较简单：
public static final Parser<Int> unsignedInt = digits1plus.filter(digits -> digits.first() != '0').map(Int::unsigned);
有符号整数，则是符号位后面紧跟一个无符号整数：
public static final Parser<Int> signedInt = seq(flag, unsignedInt, Int::signed);
无符号浮点数的情况比无符号整数复杂一点，需要考虑是否包含小数点，有小数点的话，要考虑小数点前是否有数字。一个方法是给每种情况定义一个专门的parser，然后or组合构成最终的无符号浮点数parser：
// 包含整数部分的无符号浮点数
public static final Parser<Float> fullUnsignedFloat =
seq(digits1plus, point.then(digits0plus), Float::full);
// 不含整数部分的无符号浮点数
public static final Parser<Float> onlyFractionPartUnsignedFloat =
point.then(digits1plus).map(Float::onlyFractionPart);
// 只含整数部分的无符号浮点数
public static final Parser<Float> onlyIntPartUnsignedFloat =
digits1plus.map(Float::onlyIntPart);
// 任意无符号浮点数
public static final Parser<Float> unsignedFloat =
fullUnsignedFloat.or(onlyFractionPartUnsignedFloat).or(onlyIntPartUnsignedFloat);
类似的，正确的科学计数可能只包含浮点数部分，也可能由浮点数部分和指数部分共同组成：
// 包含指数部分的科学计数
public static final Parser<Number> withExpNumber = seq(floatParser, expFlag.then(signedInt),
Number::full);
// 不包含指数部分的科学计数
public static final Parser<Number> justFloatNumber = floatParser.map(Number::justFloat);
// 任意科学计数
public static final Parser<Number> number = withExpNumber.or(justFloatNumber);
leetcode的题目中，允许数字前后出现任意多个空格：
public static final Parser<Number> numberSurroundWithSpaces = number.surroundWith(spaces);
至此，我们就完成了一个用于求解原面试题的数字parser，不过原题中只需要验证是否可以解析得到正确的科学计数，所以最终solution方法为：
public boolean isNumber(String s) {
return numberSurroundWithSpaces.parse(s).isSucceed();
}
总结
我们花了很大篇幅用来构建一个简单的类parsec库，然后在这个库的基础上，用声明式语法构建了一个科学计数解析器。对于一道面试题来说，确实有大动干戈的嫌疑（我最终AC的solution行数为400，执行时间也排在末尾5%, 而推荐题解只有36行）。但实际上，对于绝大部分现代程序员来说，日常工作中最大的挑战，不是如何优化代码的执行复杂度（怎么写执行更快），而是优化代码的逻辑复杂度（怎么写更容易读懂），即如何让你的代码不会比业务逻辑本身更复杂，更难以理解。从这个角度考虑，函数式编程是我们的不二之选：它对副作用的谨慎对待让我们更容易写出安全、稳定的代码；它对高阶函数的提倡，把依赖经验口口相传的设计模式落地到具体的代码中，在类型系统的加持下，我们可以顺利地打造各个问题领域的乐高世界。
