6

Haskell の宿題の最後の部分を完了しようとしていますが、これまでのコードで行き詰まっています。

data Entry = Entry (String, String)

class Lexico a where
    (<!), (=!), (>!) :: a -> a -> Bool

instance Lexico Entry where
    Entry (a,_) <! Entry (b,_) = a <  b
    Entry (a,_) =! Entry (b,_) = a == b
    Entry (a,_) >! Entry (b,_) = a >  b

entries :: [(String, String)]
entries =  [("saves", "en vaut"), ("time", "temps"), ("in", "<`a>"),
              ("{", "{"), ("A", "Un"), ("}", "}"), ("stitch", "point"),
              ("nine.", "cent."), ("Zazie", "Zazie")]

build :: (String, String) -> Entry
build (a, b) = Entry (a, b)

diction :: [Entry]
diction = quiksrt (map build entries)

size :: [a] -> Integer
size [] = 0
size (x:xs) = 1+ size xs

quiksrt :: Lexico a => [a] -> [a]
quiksrt [] = []
quiksrt (x:xs)
    |(size [y|y <- xs, y =! x]) > 0 = error "Duplicates not allowed."
    |otherwise = quiksrt [y|y <- xs, y <! x]++ [x] ++ quiksrt [y|y <- xs, y >! x] 


english :: String
english = "A stitch in time save nine."

show :: Entry -> String
show (Entry (a, b)) = "(" ++ Prelude.show a ++ ", " ++ Prelude.show b ++ ")"

showAll :: [Entry] -> String
showAll [] = []
showAll (x:xs) = Main.show x ++ "\n" ++ showAll xs

main :: IO ()
main = do putStr (showAll ( diction ))

質問は尋ねます：

英文 'english' を取得し、二分探索を使用して英仏辞書の各単語を検索し、単語ごとの置換を実行し、フランス語の翻訳を組み立てて出力する Haskell プログラムを作成します。

関数 'quicksort' は重複するエントリを ('error'/abort で) 拒否するため、英語の単語に対して正確に 1 つのフランス語の定義が存在します。元の 'raw_data' と '("saves", "sauve")' を 'raw_data' に追加した後の両方で 'quicksort' をテストします。

これは、二分探索のフォン ノイマン遅延停止バージョンです。Haskell へのリテラル音訳を行います。Haskell バージョンは、入力直後に再帰的な「ループ不変条件」を検証する必要があり、保持できない場合は「エラー」/中止で終了します。英単語が見つからない場合も同様に終了します。

function binsearch (x : integer) : integer
local j, k, h : integer
j,k := 1,n
do j+1 <> k --->
  h := (j+k) div 2
  {a[j] <= x < a[k]}        // loop invariant
  if x <  a[h] ---> k := h
   | x >= a[h] ---> j := h
  fi
od
{a[j] <= x < a[j+1]}        // termination assertion
found := x = a[j]
if found     ---> return j
 | not found ---> return 0
fi

ハスケル版では

binsearch :: String -> Integer -> Integer -> Entry

タイプ '[Entry]' の定数辞書 'a' はグローバルに可視であるためです。ヒント: 「binsearch」と入力したら、すぐに文字列 (英単語) を「エントリ」にします。

高水準データ型 'Entry' のプログラミング値は、整数に対してこれら 2 つの関数を設計できれば、それらを持ち上げて Entry を操作するのは簡単だということです。

バイナリサーチ機能をどのように使用するべきか知っている人はいますか?

4

4 に答える 4

4

インストラクターは「リテラル音訳」を要求するので、同じ変数名を同じ順序で使用します。ただし、いくつかの違いに注意してください。

  • 指定されたバージョンは 1 つのパラメーターしか取りませんが、彼が与える署名には 3 つが必要です。うーん、
  • 指定されたバージョンは再帰的ではありませんが、彼は再帰的バージョンを要求しています。

別の回答では、配列に変換するように言われていますが、このような小さな演習 (結局これは宿題です) では、リストが直接アクセスできるふりをすることができると感じました。私はちょうどあなたの diction::[Entry] を取り、それに索引を付けました。いくつかの場所で Int と Integer の間で変換する必要がありました。

マイナーな問題: 英語の値にタイプミスがあります (bs は私が作成した binSearch へのショートカットです):

  *Main> map bs (words english)
[Entry ("A","Un"),Entry ("stitch","point"),Entry ("in","<`a>"),Entry ("time","te
mps"),*** Exception: Not found
*Main> map bs (words englishFixed)
[Entry ("A","Un"),Entry ("stitch","point"),Entry ("in","<`a>"),Entry ("time","te
mps"),Entry ("saves","en vaut"),Entry ("nine.","cent.")]
*Main>
于 2008-11-16T06:01:25.490 に答える
3

二分探索にはランダム アクセスが必要ですが、これはリストでは不可能です。したがって、最初に行うことは、おそらくリストをArray(with listArray) に変換し、それに対して検索を行うことです。

于 2008-11-16T00:28:53.900 に答える
0

重要な Prelude 演算子は次のとおりです。

(!!) :: [a] -> Integer -> a
-- xs!!n returns the nth element of xs, starting at the left and
-- counting from 0.

したがって、[14,7,3]!!1~~> 7 です。

于 2009-11-08T22:47:15.120 に答える