我開始在Haskell中做我的第一個步驟。我過去曾用Python處理過遞回問題。 只是為了練習，我想寫一個函式巫師反轉一個串列：
reverse2 lst = if length lst == 1
then lst ! 0 then lst !
else (last lst) : (reverse2 (init lst))
我得到的錯誤是：
SimpleFunctions.hs：9：22：錯誤。
- Occurs檢查：無法構建無限的type: a ~ [a]
- In運算式。(last lst) : (reverse2 (init lst))
In運算式。
if length lst == 1 then
lst ! 0 then lst!
else[/span
(last lst) : (reverse2 (init lst))
在'reverse2'的方程式。
reverse2 lst
= if length lst == 1 then
lst ! 0 then lst !
else[/span
(last lst) : (reverse2 (init lst))
- 相關的系結包括
lst :: [a] （系結在SimpleFunctions.hs:7:10）。
reverse2 :: [a] -> [a] (系結在SimpleFunctions.hs:7:1)
|
9 | else (last lst) : (reverse2 (init lst) )
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Failed, no modules loaded.
但是如果我通過
改變reverse2 lst = if null lst
then [] 。
else (last lst) : (reverse2 (init lst))
它起作用了！
為什么第一個選項不正確？
uj5u.com熱心網友回復：
你用lst ! 0，但這將回傳串列的一個元素，而不是串列本身。因此，你應該包住串列中的第一個專案，例如：
reverse2 :: [a] -> [a)
reverse2 lst = if length lst == 1
then [lst !0]
else (last lst) : (reverse2 (init lst))然而，這的時間復雜度是O(n2)，因為確定串列的長度，并獲得最后項需要線性時間，而且我們必須對所有專案都這樣做。
通常情況下，這個問題是通過利用accumulator來解決的：一個額外的引數來存盤到目前為止的反轉串列，并通過一個稍微改變的累積器來進行遞回呼叫，直到我們到達串列的末端。
在這種情況下，我們就將reverse實作為：
reverse :: [a] -> [a)
reverse = go [] 。
where go rv [] = rv
go rv (x:xs) = go (x:rv) xs這里rv是迄今為止得到的串列的反向。對于串列中的每一個專案，我們用該專案預置反向串列。如果串列是這樣的 [1,4,2,5]，那么我們將進行遞回呼叫，看起來像：
reverse [1, 4,2,5]
→去 [] [1,4,2,5]
→去 [1] [4,2,5]
→去 [4,1] [2,5]
→去 [2,4, 1] [5]
→去 [5,2,4, 1] []
→ [1,4,2,5] uj5u.com熱心網友回復：
讓我們為你的函式寫出一個型別。一個反向函式接收一個串列并回傳一個串列。所以類似于
的東西reverse2 :: [a] -> [a)
現在，讓我們看一下實作。
reverse2 lst = if length lst == 1
then lst ! 0 then lst!
else (last lst) : (reverse2 (init lst))
if的兩個臂膀都需要回傳一個[a]，因為那是預期的型別。else分支很好；它進行了一個遞回呼叫，然后預置了一個元素。我們得到的結果是一個串列。很好! 另一方面，then 分支是有問題的。lst是一個[a]，而(!!)有型別
(!):: [a] -> Int -> a
所以lst ! 0的型別是a，而不是[a]。為了回傳一個單子串列，我們需要明確地說明它。
reverse2 lst = if length lst == 1
then [lst !0]
else (last lst) : (reverse2 (init lst))
當然，現在這個函式在空串列上會失敗，因為在空串列上取last和init會失敗。所以我們需要一個空串列的案例。
reverse2 :: [a] -> [a)
reverse2 [] = [] 。
reverse2 lst = if length lst == 1
then [lst !0]
else (last lst) : (reverse2 (init lst))
而在這一點上，你的null解決方案看起來更簡單。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/316941.html
標籤：