4

私は末尾再帰を学習していますが、関数が末尾再帰であるかどうかを判断するのにいくつかの問題があります（主に別の関数を使用する関数で）。

次の2つの関数を実装しましたが、末尾再帰であるかどうかはわかりません。

1つ目は、2つのリストを連結する関数です。

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）

2番目の機能は、指定されたリスト内の指定された番号の最初の出現を削除することです。

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)
        | otherwise = remov n t 0 (h:result)

remove n list = remov n list 0 []

パラメータaux（値として0または1を想定できます）は、オカレンスが削除されたかどうかをマークするために使用されています。

remove関数では、再帰呼び出しを介して部分的な結果が渡されている間、リストは反転されます。最後に、リストは最初の出現がなく、逆さまになっているため、結果として返されるように反転する必要があります。

4

1 に答える 1

6 
conca (h:t) result = conca (init (h:t)) ( last(h:t):result )

is a tail call, but last(h:t):result starts life as an unevaluated thunk, so it's a (hand-wavy) bit like these nested function calls are on the stack still.

conca pattern matches on its first argument so init will be evaluated in the recursive call.

conca is non-strict in its second argument, so those thunks won't get evaluated while applying the recursive call of conca.

remov is tail recursive, yes, but....

Use True and False instead of 0 and 1 to make your code clearer:

remov n [] found result = invert result []
remov n (h:t) found result
        | found = remov n t True (h:result)
        | n==h = remov n t True (result)
        | otherwise = remov n t False (h:result)

remove n list = remov n list False []

This would be better not passing around so much data, reducing the copying of n and using two functions instead of a single function that tests a boolean parameter:

remove' n list = seek list [] where
   seek []     result = invert result []
   seek (h:t) result | h == n    = got t result
                     | otherwise = seek t (h:result)
   got []    result = invert result []
   got (h:t) result = got t (h:result)

but got a result just calculates reverse result ++ a, so you could write

remove'' n list = seek list [] where
   seek []     result = invert result []
   seek (h:t) result | h == n    = invert result [] ++ t
                     | otherwise = seek t (h:result)

However, it all seems rather a lot of effort, and still traverses the list twice. Why not go for a non-tail call:

removeFast n [] = []
removeFast n (h:t) | h == n = t
                   | otherwise = h:removeFast n t

This has the benefit of producing its first element straight away rather than running the whole list, and short cuts to return t without further computation once it's found the element to remove. Try racing length (removeFast 1 [1..100000]) against length (remove 1 [1..100000]) (vary the number of zeros according to your processor speed).

If you want to make a more efficient tail recursive conca, you could use the trick from remove:

conc this result = prepend (invert this []) result

prepend [] result = result
prepend (h:t) result = prepend t (h:result)

As before, you're traversing this twice, once inverting it, the other prepending it, but that's still a linear algorithm, and much better than using init and last for each element, which is quadratic.

于 2012-12-19T02:55:56.843 に答える