如何在不使用额外空间的情况下反转堆栈... fp-style

Question

我试图深入探索FP，稍微深入地图表面 - 减少我最近大部分时间做的东西 - 是的，我知道还有更多，因此...

无论如何，命令式编程中的一个经典问题是堆栈反转“不使用额外空间”。该解决方案通常使用双递归调用堆栈来访问堆栈的底部，获取底层元素，并将其返回到外部递归，以相反的顺序重新构建堆栈。我一直在试图解决Haskell中的同一个问题，但我无法弄清楚如何用该语言来表达它。提示？使用额外的空间

编辑是，使用堆栈为，问题往往是在考试和面试来看看人们如何看待的东西一招一个。另外，是的，我知道东西是不可变的，所以创建一个与给定的相反的重复堆栈显然是可以接受的。

（顺便说一句，你们已经失败了采访......，JK）

Answer 1

的唯一有效的方法来扭转名单

reverse = revApp [] 

revApp acc [] = acc 
revApp acc (x:xs) = revApp (x:acc) xs 

有各种不同的方式来表达这种想法，但他们都导致基本相同的代码。这个想法是从前到后（从堆栈语言，从上到下）解构列表，并从后到前构建新列表。

---

有没有办法从从前到后完全正常工作，因为你不知道逆转列表的第一个元素是什么，直到你看到的参数列表的最后一个元素。如果你愿意，你可以可以从前到后建立结果列表的结构。这会稍微慢一些。

lazyReverse xs = zipWith' (flip const) xs (reverse xs) 

zipWith' _ [] _ = [] 
zipWith' f (x:xs) ~(y:ys) = f x y : zipWith' f xs ys 

的想法是通过复制参数列表的结构（从前到后），而是从相反副本得到其值形成结果列表的结构。我不认为有任何方法可以避免这种堆分配。中间代表每个尾部的thunk捕获对事物的引用，因此它们必须位于堆上而不是堆栈中。