示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载导读本篇文章围绕《Functional Programming in Scala》配套仓库 fpinscala 中解析器章节的练习 17 展开。该练习要求为解析器增加一个isSliced状态位并把单纯的Location升级为ParseState从而让slice组合子在不构建中间值的前提下高效切取原始输入。读完本文你将理解Sliceable实现中ParseState、Slice构造器与各组合子改造的完整设计逻辑并能对照Reference实现评估两种方案的差异。练习 17 的定位从能跑到跑得快在 fpinscala 的解析器练习序列中前面的练习如 15、16 题已经完成了Parserstrait 的基本骨架与Reference参考实现——一个以Location Result[A]为核心的状态动作模型。练习 17 的提示非常精炼Try adding another piece of state toLocation,isSliced. You may want to renameLocationtoParseState, as its no longer just the location!也就是说这一步要做两件事新增状态给位置信息增加一个isSliced布尔标志标记当前解析器是否处于slice包裹之下重命名类型既然它不再只是位置就应改名为ParseState。完整答案位于 Sliceable.scala与 Reference.scala 形成对照。下面的所有分析均以该文件为准。为什么需要 slice避免构建注定被丢弃的值先看Reference中朴素版的slicedef slice: Parser[String] l p(l) match case Success(_, n) Success(l.slice(n), n) case f Failure(_, _) f它的做法是先运行内部解析器p得到成功值例如map已经构造好的List[A]再丢弃这个值、仅保留消费长度n最后用Location.slice(n)重新切出子串。问题很明显值被白白构造了一遍又原样扔掉。当many反复累积成百上千个元素、而这些元素最终只用于计算长度或根本不参与结果时这种浪费尤为突出。Sliceable的思路是如果解析器知道自己处于slice上下文中就干脆不构造值只回报消费的字符数由最外层的slice一次性切出原始输入。为此需要两处结构性改造——ParseState与Slice。核心改造一从 Location 到 ParseStatecase class ParseState(loc: Location, isSliced: Boolean): def advanceBy(numChars: Int): ParseState copy(loc loc.advanceBy(numChars)) def input: String loc.input.substring(loc.offset) def unslice copy(isSliced false) def reslice(s: ParseState) copy(isSliced s.isSliced) def slice(n: Int) loc.input.substring(loc.offset, loc.offset n)Location本身定义在 Parsers.scala负责记录输入串与偏移量并派生出line、col、currentLine、columnCaret等用于错误报告的信息。ParseState在它之上叠加了一个布尔标志并提供四个便捷方法advanceBy消费numChars个字符后前进到新状态input当前剩余输入unslice临时关闭 slice 标志flatMap会用到reslice(s)把isSliced恢复为另一个状态的值flatMap恢复第二段解析器时用到slice(n)从当前位置切出n个字符。类型别名也随之变化type Parser[A] ParseState Result[A]核心改造二Result 新增 Slice 构造器GADTenum Result[A]: case Success(get: A, length: Int) case Failure(get: ParseError, isCommitted: Boolean) extends Result[Nothing] case Slice(length: Int) extends Result[String]这是整个实现中最讲究的一处Result成了一个 GADT广义代数数据类型因为并非所有构造器共享同一类型参数——Slice把类型参数A特化为String。这意味着当模式匹配命中Slice时编译器能推断出A就是String从而允许在map、map2中安全地调用f(s.slice(n))。Result上的辅助函数也相应扩充extract(input)把三种结果统一还原为Either[ParseError, A]。对Slice(length)直接Right(input.substring(0, length))slice把Success或已有的Slice统一转换为Sliceuncommit供attempt使用把已提交失败降级为未提交addCommit供flatMap传播是否已消费输入信息mapError供scope/label改写错误advanceSuccess(n)成功与 slice 的结果都累加消费长度注意Slice分支也要累加。组合子逐个改造sliced 与 unsliced 双路径原语解析器string 与 regexdef string(w: String): Parser[String] s val i firstNonmatchingIndex(s.loc.input, w, s.loc.offset) if i -1 then if s.isSliced then Slice(w.length) else Success(w, w.length) else Failure(s.loc.advanceBy(i).toError(s$w), i ! 0) def regex(r: Regex): Parser[String] s r.findPrefixOf(s.input) match case None Failure(s.loc.toError(sregex $r), false) case Some(m) if s.isSliced then Slice(m.length) else Success(m, m.length)要点在isSliced为真时成功分支直接返回Slice(长度)而不携带字符串值。regex的失败保持未提交注释明确说明regex 匹配是全有或全无的string则根据是否消费了前缀决定提交与否。slice 组合子本身def slice: Parser[String] s p(s.copy(isSliced true)).slice这是整个机制的开关把内部解析器置于isSliced true下运行再把结果Slice、Success或Failure通过Result.slice统一规约为Slice。消费长度由内层原语累积而来外层 slice 在run阶段通过extract一次性切出原始输入。map命中 Slice 时按需切串override def mapB: Parser[B] s p(s) match case Success(a, n) Success(f(a), n) case Slice(n) Success(f(s.slice(n)), n) case f Failure(_, _) f在Slice分支利用 GADT 类型细化调用s.slice(n)从原始输入切出String再交给f。注意此时已经退出了 slice 模式返回普通Success因为f的结果是真正需要保留的值。map2四条路径的精细处理override def map2B, C(f: (A, B) C): Parser[C] s p(s) match case Success(a, n) val s2 s.advanceBy(n) p2(s2) match case Success(b, m) Success(f(a, b), n m) case Slice(m) Success(f(a, s2.slice(m)), n m) case f Failure(_, _) f case Slice(n) val s2 s.advanceBy(n) p2(s2) match case Success(b, m) Success(f(s.slice(n), b), n m) case Slice(m) if s.isSliced then Slice(n m).asInstanceOf[Result[C]] else Success(f(s.slice(n), s2.slice(m)), n m) case f Failure(_, _) f case f Failure(_, _) f需要处理第一个解析器是否 sliced × 第二个解析器是否 sliced的四种组合。最有趣的是两个都是Slice的分支如果当前整体仍处于 slice 上下文直接把消费长度相加返回Slice(n m)注意这里需要asInstanceOf因为Slice的类型是Result[String]而map2期望Result[C]否则才真正切串构造f的结果。flatMapunslice 与 reslice 的微妙舞蹈def flatMapB: Parser[B] s p(s.unslice) match case Success(a, n) f(a)(s.advanceBy(n).reslice(s)) .addCommit(n ! 0) .advanceSuccess(n) case Slice(n) f(s.slice(n))(s.advanceBy(n).reslice(s)).advanceSuccess(n) case f Failure(_, _) f注释解释了为什么这里如此微妙要生成第二个解析器必须先拿到A的值因此即使整体处于 slice 上下文中第一个解析器也必须以unslice方式运行一旦拿到A生成了第二个解析器就可以通过reslice(s)把 slice 标志恢复给第二个解析器。文件注释还诚实指出在第二个解析器的选择不依赖第一个解析器如map2的场景下这种实现不如全程 sliced高效——这是以通用性换取的取舍。many循环累积避免栈溢出override def many: Parser[List[A]] s var nConsumed: Int 0 if s.isSliced then def go(p: Parser[String], offset: Int): Result[String] p(s.advanceBy(offset)) match case f Failure(e, true) f case Failure(e, _) Slice(offset) case Slice(n) go(p, offset n) case Success(_, _) sys.error(sliced parser should not return success, only slice) go(p.slice, 0).asInstanceOf[Result[List[A]]] else val buf new collection.mutable.ListBuffer[A] def go(p: Parser[A], offset: Int): Result[List[A]] p(s.advanceBy(offset)) match case Success(a, n) buf a go(p, offset n) case f Failure(e, true) f case Failure(e, _) Success(buf.toList, offset) case Slice(n) buf s.input.substring(offset, offset n) go(p, offset n) go(p, 0)与Reference的many相同这里用可变ListBuffer配合循环避免朴素递归的栈溢出。slice 模式下内部解析器被p.slice包裹期望只返回Slice若返回Success直接报错因为它违背了不构造值的约定成功则只累加 offset非 slice 模式下Slice分支仍需从输入切出字符串放入缓冲区。or / attempt提交机制不变or与attempt的语义与Reference完全一致or只在第一个解析器未提交失败Failure(e, false)时才尝试p2attempt通过uncommit把已提交失败降级。它们与 slice 机制正交无需特殊处理。run 入口一切回到 Eitherdef run(s: String): Either[ParseError, A] p(ParseState(Location(s), false)).extract(s)入口以isSliced false初始化状态因此普通运行完全走非 slice 路径只有当某处显式调用slice后内部解析器才进入高效模式最终由extract从原始输入切出字符串。这一设计与 Parsers.scala 中 trait 声明的run签名保持一致。与前后练习的关联练习 16负责ParseError与Location的错误报告能力如push、label、collapseStack与 caret 定位是ParseState得以工作的基础答案见 16.answer.md练习 18在ParseError上追加otherFailures: List[ParseError]以收集or各分支的错误hint 见 18.hint.md与 17 题一样都属于为组合子体系补足工程化能力的系列改造练习版骨架中ParseError已预留otherFailures字段而Location的remaining、slice留作练习填空见 练习版 Parsers.scala。实战验证JSON 解析器中的应用Sliceable的实用价值在 JSON.scala 中可见一斑*、*、token等组合子都会把不关心其结果的那一侧用slice包裹见 Parsers.scala 的*与*默认实现例如def *B p.slice.map2(p2)((_, b) b)。在解析{ Company name : Microsoft Corporation, ... }这类含大量分隔符、空白与标点的 JSON 文档时slice让这些被忽略的片段不再被逐个构造再丢弃。测试套件 JSONSuite.scala 验证了嵌套对象、数组、各字面量与畸形输入的错误路径可作为组合子行为正确性的参考基准。小结练习 17 的改造核心可概括为三句话状态升级Location→ParseState(loc, isSliced)用布尔标志宣告我处于 slice 上下文结果特化Result增加Slice(length)构造器让被忽略的解析在成功时只回报消费长度、不构造值组合子双路径string/regex按标志决定返回值map/map2按需切串flatMap以unslice/reslice平衡通用性与效率many以循环规避栈溢出。这一设计既保留了组合子 API 的完整性与定律又让解析器在只关心长度、不关心内容的场景下获得数量级层面的分配节省是理解函数式解析器工程化落地的关键一课。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala Traverse 练习 17 详解如何用 mapAccum 实现 foldLeftfpinscala Traverse 练习 17 详解如何用 mapAccum 实现 foldLeft 导读 本文围绕《Functional Programm示例工程fpinscala 第 12 章练习 9 深度解析用 map2 与 unit 组合两个 Applicativecompose 实现fpinscala 第 12 章练习 9 深度解析用 map2 与 unit 组合两个 Applicativecompose 实现 导读 本文围绕 fpi示例工程用 runFree 与 runTrampoline 实现 Free 单子翻译translate——fpinscala 第 13 章练习 4 深度解析用 runFree 与 runTrampoline 实现 Free 单子翻译translate——fpinscala 第 13 章练习 4 深度解析 本篇技示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考