我是Haskell的新手。我试图了解Haskell如何处理递归函数调用以及它们的惰性评估。我进行的实验很简单，即在C++和Haskell中构建二叉搜索树，并分别按后序遍历它们。C++实现是标准的辅助堆栈方法。(我只是在访问元素时打印出它)。
这是我的Haskell代码：
module Main (main) where
import System.Environment (getArgs)
import System.IO
import System.Exit
import Control.Monad(when)
import qualified Data.ByteString as S
main = do
args <- getArgs
when (length args < 1) $ do
putStrLn "Missing input files"
exitFailure
content <- readFile (args !! 0)
--preorderV print $ buildTree content
mapM_ print $ traverse POST $ buildTree content
putStrLn "end"
data BSTree a = EmptyTree | Node a (BSTree a) (BSTree a) deriving (Show)
data Mode = IN | POST | PRE
singleNode :: a -> BSTree a
singleNode x = Node x EmptyTree EmptyTree
bstInsert :: (Ord a) => a -> BSTree a -> BSTree a
bstInsert x EmptyTree = singleNode x
bstInsert x (Node a left right)
| x == a = Node a left right
| x < a = Node a (bstInsert x left) right
| x > a = Node a left (bstInsert x right)
buildTree :: String -> BSTree String
buildTree = foldr bstInsert EmptyTree . words
preorder :: BSTree a -> [a]
preorder EmptyTree = []
preorder (Node x left right) = [x] ++ preorder left ++ preorder right
inorder :: BSTree a -> [a]
inorder EmptyTree = []
inorder (Node x left right) = inorder left ++ [x] ++ inorder right
postorder :: BSTree a -> [a]
postorder EmptyTree = []
postorder (Node x left right) = postorder left ++ postorder right ++[x]
traverse :: Mode -> BSTree a -> [a]
traverse x tree = case x of IN -> inorder tree
POST -> postorder tree
PRE -> preorder tree
preorderV :: (a->IO ()) -> BSTree a -> IO ()
preorderV f EmptyTree = return ()
preorderV f (Node x left right) = do
f x
preorderV f left
preorderV f right
我的测试结果表明，C++在性能方面明显优于Haskell：
C++性能：（请注意，first15000.txt大约是first3000.txt的5倍）
time ./speedTestForTraversal first3000.txt > /dev/null
real 0m0.158s
user 0m0.156s
sys 0m0.000s
time ./speedTestForTraversal first15000.txt > /dev/null
real 0m0.923s
user 0m0.916s
sys 0m0.004s
使用相同输入文件的Haskell：
time ./speedTestTreeTraversal first3000.txt > /dev/null
real 0m0.500s
user 0m0.488s
sys 0m0.008s
time ./speedTestTreeTraversal first15000.txt > /dev/null
real 0m3.511s
user 0m3.436s
sys 0m0.072s
我本以为Haskell与C++的差别不大，但是否存在一些错误？有没有办法改进我的Haskell代码？
谢谢。
编辑：2014年10月18日
经过多次测试，Haskell的遍历仍然比C++实现要慢得多。我要给予Cirdec的回答充分的信任，因为他指出了我Haskell实现的低效性。然而，我的原始问题是比较C++和Haskell实现。所以我想保留这个问题，并发布我的C++代码以鼓励更进一步的讨论。
#include <iostream>
#include <string>
#include <boost/algorithm/string.hpp>
#include <fstream>
#include <stack>
using namespace std;
using boost::algorithm::trim;
using boost::algorithm::split;
template<typename T>
class Node
{
public:
Node(): val(0), l(NULL), r(NULL), p(NULL) {};
Node(const T &v): val(v), l(NULL), r(NULL), p(NULL) {}
Node* getLeft() {return l;}
Node* getRight(){return r;}
Node* getParent() {return p;}
void setLeft(Node *n) {l = n;}
void setRight(Node *n) {r = n;}
void setParent(Node *n) {p = n;}
T &getVal() {return val;}
Node* getSucc() {return NULL;}
Node* getPred() {return NULL;}
private:
T val;
Node *l;
Node *r;
Node *p;
};
template<typename T>
void destoryOne(Node<T>* n)
{
delete n;
n = NULL;
}
template<typename T>
void printOne(Node<T>* n)
{
if (n!=NULL)
std::cout << n->getVal() << std::endl;
}
template<typename T>
class BinarySearchTree
{
public:
typedef void (*Visit)(Node<T> *);
BinarySearchTree(): root(NULL) {}
void delNode(const T &val){};
void insertNode(const T &val){
if (root==NULL)
root = new Node<T>(val);
else {
Node<T> *ptr = root;
Node<T> *ancester = NULL;
while(ptr && ptr->getVal()!=val) {
ancester = ptr;
ptr = (val < ptr->getVal()) ? ptr->getLeft() : ptr->getRight();
}
if (ptr==NULL) {
Node<T> *n = new Node<T>(val);
if (val < ancester->getVal())
ancester->setLeft(n);
else
ancester->setRight(n);
} // else the node exists already so ignore!
}
}
~BinarySearchTree() {
destoryTree(root);
}
void destoryTree(Node<T>* rootN) {
iterativePostorder(&destoryOne);
}
void iterativePostorder(Visit fn) {
std::stack<Node<T>* > internalStack;
Node<T> *p = root;
Node<T> *q = root;
while(p) {
while (p->getLeft()) {
internalStack.push(p);
p = p->getLeft();
}
while (p && (p->getRight()==NULL || p->getRight()==q)) {
fn(p);
q = p;
if (internalStack.empty())
return;
else {
p = internalStack.top();
internalStack.pop();
}
}
internalStack.push(p);
p = p->getRight();
}
}
Node<T> * getRoot(){ return root;}
private:
Node<T> *root;
};
int main(int argc, char *argv[])
{
BinarySearchTree<string> bst;
if (argc<2) {
cout << "Missing input file" << endl;
return 0;
}
ifstream inputFile(argv[1]);
if (inputFile.fail()) {
cout << "Fail to open file " << argv[1] << endl;
return 0;
}
while (!inputFile.eof()) {
string word;
inputFile >> word;
trim(word);
if (!word.empty()) {
bst.insertNode(word);
}
}
bst.iterativePostorder(&printOne);
return 0;
}
编辑：2014年10月20日 下方Chris的答案非常详尽，我可以重复这个结果。
postorder (Node x left right) = postorder left ++ postorder right ++ [x]吗？ - Cirdec