0

末尾再帰を使用して特定の要素のインデックスを見つける関数を作成しようとしています。リストにからまでの数字が含まれてい1て10、を検索しているとすると5、出力はになります4。私が抱えている問題は、末尾再帰を使用して「カウント」することです。ただし、この場合、再帰呼び出しの数を手動で「カウント」する必要があるかどうかさえわかりません。!!特定の位置にある要素を返すため、役に立たないものを使用してみました。特定の要素の位置を返す関数が必要です（正反対）。

私はこれを何時間も理解しようとしてきました。

コード：

  whatIndex a [] = error "cannot search empty list"
  whatIndex a (x:xs) = foo a as
    where
       foo m [] = error "empty list"
       foo m (y:ys) = if m==y then --get index of y
                         else foo m ys

注：ライブラリ関数を使用せずにこれを実装しようとしています

4

2 に答える 2

5

ヘルパー関数には、カウント用の追加パラメーターが必要です。

whatIndex a as = foo as 0
  where
    foo [] _ = error "empty list"
    foo (y:ys) c
        | a == y    = c
        | otherwise = foo ys (c+1)

Maybeところで、エラーを使用するのではなく、この関数に戻り型を与える方が良い形式です。elemIndex正当な理由で、それもどのように機能するかです。これは次のようになります

whatIndex a as = foo as 0
  where
    foo [] _ = Nothing
    foo (y:ys) c
        | a == y    = Just c
        | otherwise = foo ys (c+1)
于 2013-02-13T00:20:15.570 に答える
3

注：ライブラリ関数を使用せずにこれを実装しようとしています

これは一般的には良い考えではありません。より良い演習はこれです：

  1. ライブラリ関数を使用してそれを実装する方法を理解します。
  2. 手順1で使用したライブラリ関数を自分で実装する方法を理解します。

このようにして、3つの重要なスキルを学びます。

  • 標準ライブラリ関数とは何ですか、そしてそれらがいつ役立つかの例。
  • 問題を細かく分割する方法
  • ライブラリにあるような基本的な関数の書き方。

ただし、この場合、はとほぼwhatIndex同じ関数elemIndexでData.Listあるため、問題はこのライブラリ関数の独自のバージョンを作成することになります。

ここでの秘訣は、リストを繰り返しながらカウンターをインクリメントすることです。末尾再帰関数を作成するための標準的な手法があります。これは、累積パラメーターと呼ばれます。それはこのように動作します：

  1. 「フロントエンド」関数と比較して、追加の情報を追跡するために追加のパラメーター（またはそれ以上）を受け取る補助関数を作成します。
  2. 次に、「実際の」関数を補助関数の呼び出しとして定義します。

したがって、elemIndexの場合、補助関数は次のようになります（i現在の要素インデックスの累積パラメータとして）：

-- I'll leave the blanks for you to fill.
elemIndex' i x []      = ...
elemIndex' i x (x':xs) = ...

次に、「ドライバー」機能は次のとおりです。

elemIndex x xs = elemIndex 0 x xs

しかし、ここで私が言及しなければならない深刻な問題があります：この関数をHaskellでうまく機能させるのは難しいです。末尾再帰は、厳密な（遅延のない）関数型言語では便利なトリックですが、Haskellではそれほど多くはありません。理由は次のとおりです。

  1. Haskellの末尾再帰関数は、スタックを爆破する可能性がありますが、
  2. 非末尾再帰関数は、一定のスペースで実行できます。

私のこの古い答えは、2番目のポイントの例を示しています。

したがって、あなたの場合、非末尾再帰ソリューションは、一定のスペースで実行される（つまり、長いリストでスタックを爆破しない）、おそらく最も簡単なソリューションです。

elemIndex x xs = elemIndex' x (zip xs [0..])

elemIndex' x pairs = snd (find (\(x', i) -> x == x') pairs)

-- | Combine two lists by pairing together their first elements, their second 
-- elements, etc., until one of the lists runs out.
--
-- EXERCISE: write this function on your own!
zip :: [a] -> [b] -> [(a, b)]
zip xs ys = ...

-- | Return the first element x of xs such that pred x == True.  Returns Nothing if
-- there isn't one, Just x if there is one.
--
-- EXERCISE: write this function on your own!
find :: (a -> Bool) -> [a] -> Maybe a
find pred xs = ...
于 2013-02-13T00:43:54.340 に答える