haskell - 末尾再帰には必ずアキュムレータが必要ですか?

Question

たとえば、次の関数にはアキュムレータがないため、それでも末尾再帰ですか?

belong:: (Ord a) => a -> [a] -> Bool
belong a [] = False
belong a (h:t) 
    | a == h = True
    | otherwise = belong a t

関数内のすべての計算は再帰呼び出しの前に処理されますが、末尾再帰と見なされる十分な条件ですか?

Answer 1

末尾再帰は必ずしもアキュムレータを必要としません。アキュムレータは、再帰の各レベルで使用する余分なスペースを必要とせずに、再帰呼び出しチェーンを通じて部分的な結果を伝達する方法として末尾再帰で使用されます。たとえば、正規の末尾再帰階乗関数には、これまでに構築された部分積を伝播するためのアキュムレータが必要です。ただし、再帰呼び出しからそのサブ呼び出しまで情報を伝達する必要がない場合は、アキュムレータは必要ありません。

あなたが提供した関数は確かに末尾再帰ですが、アキュムレータを必要とせず、使用しません。リスト内の要素を検索するとき、再帰は、これまでに調べたすべての要素が検索対象の特定の要素と等しくないことを覚えておく必要はありません。検索する要素と検索するリストを知る必要があるだけです。

お役に立てれば！

Answer 2

末尾再帰は必ずしもアキュムレータを必要としません。ただし、アキュムレータがよく使用されます。ヒント、ウィキペディアの記事で「アキュムレータ」を検索してください。