Haskell不使用Prelude和模式匹配如何实现reverse函数?代码错因求解
Haskell reverse函数实现问题解答
两段代码运行差异说明
Haskell中两个列表操作运算符的类型定义是核心原因:
(:)(cons运算符)类型为a -> [a] -> [a],要求左参数是单个元素,右参数是和元素同类型的列表,作用是把元素追加到列表头部(++)(拼接运算符)类型为[a] -> [a] -> [a],要求左右参数都是同类型的列表,作用是把两个列表按顺序拼接
你写的第一段代码里,递归调用reverse1 xs返回的是已经反转完成的子列表([a]类型),[x]是把当前遍历到的单个元素包装成单元素列表,二者用++拼接完全符合类型要求,所以可以正常运行。
第二段代码的错误完全是类型不匹配导致的:你把reverse1 xs([a]类型的列表)放在了:的左参数位置,把单个元素x(a类型)放在了右参数位置,完全不符合:的参数要求,编译器会直接抛出类型错误,无法运行。
不使用++、不使用显式模式匹配的实现方案
你可以用尾递归+累加器的方案实现,全程只用:运算符,效率比用++的版本高很多,而且完全符合要求:
reverseOpt :: [a] -> [a] reverseOpt list = reverseHelper list [] where reverseHelper curr acc | null curr = acc -- 用null判断列表为空,无模式匹配 | otherwise = reverseHelper (tail curr) (head curr : acc) -- 用head/tail操作列表,全程用:拼接
这个实现的时间复杂度为O(n),远优于第一段代码O(n²)的时间复杂度,适合处理长列表。
内容的提问来源于stack exchange,提问作者Meto ballaes
相关产品推荐
相关产品推荐

