我想测试foldl vs foldr.从我所看到的,你应该使用foldl over foldr,因为尾部递归优化.
这是有道理的.但是,运行此测试后,我很困惑:
foldr(使用时间命令时需要0.057秒):
a::a -> [a] -> [a]
a x = ([x] ++ )
main = putStrLn(show ( sum (foldr a [] [0.. 100000])))
foldl(使用time命令时需要0.089s):
b::[b] -> b -> [b]
b xs = ( ++ xs). (\y->[y])
main = putStrLn(show ( sum (foldl b [] [0.. 100000])))
很明显,这个例子很简单,但我很困惑为什么foldr击败foldl.这不应该是foldl获胜的明显案例吗？
我很抱歉这样的问题.我不是太肯定的区别:,并++在Haskell运营商.
x:y:[] = [x,y]
也
[x] ++ [y] = [x,y]
至于为我提出这个问题的反向功能,
reverse ::[a]->[a]
reverse [] = []
reverse (x:xs) = reverse(xs)++[x]
以下为什么不工作？
reversex ::[Int]->[Int]
reversex [] = []
reversex (x:xs) = reversex(xs):x:[]
给出类型错误.
我对使用递归替换循环的想法感到满意.我正在摆弄一个宠物项目,我想测试一些文本输入功能,所以我写了一个小命令行界面,重复询问输入,直到它收到一个特定的退出命令.
它看起来像这样:
getCommandsFromUser = do
putStrLn "Enter command: "
keyboardInput <- getLine
let command = map toLower keyboardInput
if command == "quit"
then
putStrLn "Good-bye!"
else do
-- stuff
-- more stuff
putStrLn ("Sending command: " ++ commandURI)
simpleHTTP $ getRequest commandURI
getCommandsFromUser
main = do
getCommandsFromUser
这完全按照预期工作,但是来自C/Java背景,它仍然刺激了我大脑深处,黑暗,无意识的部分,让我想要在蜂巢中爆发,因为我不能动摇每一个递归调用的想法getCommandsFromUser正在创建一个新的堆栈框架.
现在,我对IO,monads,状态,箭头等一无所知.我还在通过Real World Haskell工作,我还没有达到那个部分,而且这些代码中的一些与我在Google上找到的东西相匹配.
另外,我知道GHC的重点在于它是一个令人抓狂的优化编译器,旨在完成令人难以置信的事情,例如美丽展开尾递归函数等.
那么有人可以解释这个实现是否"正确",如果是这样,我可以向我解释幕后会发生什么事情,如果将这个程序放在无数猴子的手中,这会阻止这个程序爆炸？
我知道尾调用优化是什么.在这种情况下,我更关心它是如何工作的,那些动作和一般功能杂质会发生什么.
这个问题并不是基于我对Haskell如何使用堆栈感到困惑的想法,而是我期望它像命令式语言一样工作; 它的基础是我不知道Haskell如何处理堆栈,并想知道它与传统的C语言有什么不同.
练习3.10表示foldRight溢出(见下图).据我所知,然而foldr在Haskell中没有.
http://www.haskell.org/haskellwiki/
-- if the list is empty, the result is the initial value z; else
-- apply f to the first element and the result of folding the rest
foldr f z [] = z
foldr f z (x:xs) = f x (foldr f z xs)
-- if the list is empty, the result is the initial value; else
-- we recurse immediately, making the new initial value the result …请考虑以下两个变体:
myReadListTailRecursive :: IO [String]
myReadListTailRecursive = go []
where
go :: [String] -> IO [String]
go l = do {
inp <- getLine;
if (inp == "") then
return l;
else go (inp:l);
}
myReadListOrdinary :: IO [String]
myReadListOrdinary = do
inp <- getLine
if inp == "" then
return []
else
do
moreInps <- myReadListOrdinary
return (inp:moreInps)
在普通的编程语言中,人们会知道尾递归变体是更好的选择.
但是,通过这个答案,显然haskell的递归实现与重复使用递归堆栈的实现并不相似.
但是因为在这种情况下,所讨论的程序涉及行动和严格的单子行列,我不确定是否适用相同的推理.事实上,我认为在这种IO情况下,尾递归形式确实更好.我不确定如何正确推理这一点.
编辑:大卫杨指出,这里最外面的电话是(>>=).即使在这种情况下,这些风格中的一种是否优于另一种？
例如,由于以下函数没有累加器,它是否仍然是尾递归的？
belong:: (Ord a) => a -> [a] -> Bool
belong a [] = False
belong a (h:t)
| a == h = True
| otherwise = belong a t
在递归调用之前处理函数中的所有计算,它是否被认为是尾递归的充分条件？
我一直试图理解Haskell中的懒惰评估,我理解它基本上只是在必要时进行评估.但是当我试图有效地实现斐波那契时,我遇到了这个(奇怪的？)行为:这个实现:
--wrapper function used by both implementations
fib :: Int -> Int
fib x = if x < 0 then 0 else fib2 0 1 x
fib2 :: Int -> Int -> Int -> Int
fib2 x y 0 = x
fib2 x y z = fib2 y (x + y) (z - 1)
即使在被召唤时也能工作
fib 20000000
> -70318061090422843
在递归调用中交换传递的参数:
fib2 :: Int -> Int -> Int -> Int
fib2 x y 0 = x
fib2 x y z = …对不起,如果已经问过这个问题,我没找到.抱歉我的英语不好.
我正在学习Haskell并尝试使用列表.我写了一个函数,它按照特定模式转换列表,我无法检查它是否现在有效,但我想是这样.
这个函数不是尾调用函数,所以我认为用一个大的列表来计算这个函数会很糟糕:
transform :: [Int] -> [Int]
transform list = case list of
(1:0:1:[]) -> [1,1,1,1]
(1:1:[]) -> [1,0,1]
[1] -> [1,1]
(1:0:1:0:s) -> 1:1:1:1: (transform s)
(1:1:0:s) -> 1:0:1: (transform s)
(1:0:s) -> 1:1: (transform s)
(0:s) -> 0: (transform s)
所以我想到了另一个功能,它会"更好":
transform = reverse . aux []
where
aux buff (1:0:[1]) = (1:1:1:1:buff)
aux buff (1:[1]) = (1:0:1:buff)
aux buff [1] = (1:1:buff)
aux buff (1:0:1:0:s) = aux (1:1:1:1:buff) s
aux buff (1:1:0:s) = aux (1:0:1:buff) s …我正在学习尾递归,我在确定我的函数是否是尾递归方面遇到了一些困难(主要是关于我使用其他函数的函数).
我已经实现了以下两个函数,但我不确定它们是否是尾递归的.
第一个是连接两个列表的函数.
conca list [] = list
conca [] result = result
conca (h:t) result = conca (init (h:t)) ( last(h:t):result )
concatenate::[a]->[a]->[a]
concatenate list1 list2 = conca list1 list2
函数中的计算在递归调用之前处理,但是它使用last和init,它们不是尾递归的(我在http://ww2.cs.mu.oz.au/172/Haskell/tourofprelude中检查了它们的定义.html)
第二个功能是删除给定列表中给定数字的第一次出现.
invert [] result = result
invert (h:t) result = invert t (h:result)
remov n [] aux result = invert result []
remov n (h:t) aux result
| aux==1 = remov n t 1 (h:result)
| n==h = remov n t 1 (result)
| …这是Clojure中插入排序的代码:
(defn in-sort! [data]
(letfn [(insert ([raw x](insert [] raw x))
([sorted [y & raw] x]
(if (nil? y) (conj sorted x)
(if (<= x y ) (concat sorted [x,y] raw)
(recur (conj sorted y) raw x )))))]
(reduce insert [] data)))
;Usage:(in-sort! [6,8,5,9,3,2,1,4,7])
;Returns: [1 2 3 4 5 6 7 8 9]
这是在Haskell中作为monoid的插入排序:
newtype OL x = OL [x]
instance Ord x => Monoid (OL x) where
mempty = OL []
mappend (OL xs) (OL ys) …