1

タスク：型アノテーションを使用して関数を作成しようとしていますminimum_recursive :: (a -> a -> Bool) -> [a] -> a。最初のパラメーターについては、2つのパラメーターを受け取る関数を受け入れ、最初のパラメーターlessが2番目のパラメーターよりも小さい場合はTrueを返し、それ以外の場合はFalseを返します。minimum_recursiveまた、2番目のパラメーターとしてリストを受け入れます。明示的な再帰を使用minimum_recursiveして、入力リスト[a]の最小値を決定する必要があります。

私の考え：実際の再帰を、アキュムレータも受け入れるヘルパー関数に入れることを考えていました。最初の項目をアキュムレータとしてヘルパー関数を呼び出します。

私がこれまでに持っているもの：これまでのところ、私は次のものを持っています：

-- function as first parameter to min'
-- accepts two params, returns True if
-- first must come before second in sorted
-- order
less :: Ord a => a -> a -> Bool
less a b = a < b

-- Subpart B
minimum_recursive :: (a -> a -> Bool) -> [a] -> a
minimum_recursive func list = minimum_recursive_h func list []

書き始める方法さえわからないのminimum_recursive_hです。

注：このタスクを実行するためのより簡単な方法があることはわかっていますが、上記のように実行する必要があります。

4

3 に答える 3

2

あなたはこのようにそれを行うことができます：

minimum_recursive _ [] = error "no minimum of empty list"
minimum_recursive _ [x] = x
minimum_recursive f (x:xs) = let m = minimum_recursive f xs
                             in if f x m then x else m

または、アキュムレータを使用します。

minimum_recursive _ [] = error "no minimum of empty list"
minimum_recursive f (x:xs) = helper f x xs
    where
      helper _ m [] = m
      helper f m (x:xs) 
          | f m x = helper f m xs
          | otherwise = helper f x xs
于 2012-04-11T17:58:15.423 に答える
1

問題を再帰的に解決する古典的な方法は次のとおりです。

  1. 最後のステップを除いて、問題はほぼ解決したと想定します。
  2. 最終ステップを除くすべての解が与えられた場合に、その最終ステップによって生成された解を計算するコードを記述します。
  3. ベースケースを書いてください。

リストの場合、これは次のパターンに変換されます。

  1. 基本ケース：解決策は何のためにあるべき[]ですか？（どちらかといえば、あなたのminimum_recursive関数の場合、これはエラーになります）。
  2. 空でないリストx:xsの場合、すでに持っていると仮定しますalmostTheResult = minimum_recursive f xs。それを踏まえてどのように計算minimum_recursive (x:xs)しますか？

私はあなたに大きなヒントを与えます：あなたはこの関数minimum_recursiveの観点から実装することができます：foldr

minBy :: (a -> a -> Bool) -> a -> a -> a
minBy pred x y = if pred x y then x else y

このfoldr関数は、私が上で説明したことを正確に実行します。の最初の引数foldrは、リストの先頭と末尾の部分解を指定して最終的な解を計算する関数であり、2番目の引数は結果の基本ケースです。

于 2012-04-11T18:49:54.170 に答える
1

リスト内で最小の要素が必要な場合は、現在持っている最小の要素をパラメーターとして関数に追加することをお勧めします。

minimum_recursive :: (a -> a -> Bool) -> a -> [a] -> a
minimum_recursive f min [] = min
minimum_recursive f min (x:xs) | f min x   = minimum_recursive f min xs
                               | otherwise = minimum_recursive f x   xs

空のリストには最小の要素がないため、aこれを呼び出す関数のタイプもからに変更する必要があります。ここに多分についてのいくつかの助けMaybe a

追加のパラメーターなしでそれを実行したい場合は、リストの先頭に最小の要素を格納することもできます。この場合、多分使用することが重要です

minimum_recursive :: (a -> a -> Bool) -> [a] ->Maybe a
minimum_recursive f [] = Nothing
minimum_recursive f (x:[]) = Just x
minimum_recursive f (y:(x:xs)) | f y x     = minimum_recursive f (y:xs)
                               | otherwise = minimum_recursive f (x:xs)

これは、最小値をehitfoldで見つける方法です。機能プログラミングの美しさを見てください。しかし、これは空のリストでは機能しません

simplefold :: [a] -> a
simplefold (x:xs) = foldl min x xs

ただし、この関数を、リストが空かどうかをチェックし、その場合はNothingを返す関数に埋め込むことができます。

betterfold :: [a] -> Maybe a
betterfold [] = Nothing
beterfold l   = Just (simplefold l)
于 2012-04-11T17:44:48.510 に答える