0

この関数をhaskellで書きたい

o(m+n) の複雑さを持つ和集合関数です。

int printUnion(int arr1[], int arr2[], int m, int n)
{
  int i = 0, j = 0;
  while(i < m && j < n)
  {
    if(arr1[i] < arr2[j])
      printf(" %d ", arr1[i++]);
    else if(arr2[j] < arr1[i])
      printf(" %d ", arr2[j++]);
    else
    {
      printf(" %d ", arr2[j++]);
      i++;
    }
  }

  /* Print remaining elements of the larger array */
  while(i < m)
   printf(" %d ", arr1[i++]);
  while(j < n)
   printf(" %d ", arr2[j++]);
}
4

1 に答える 1

5 
import Control.Monad (mapM_)

プログラミング言語の違いは、異なるプログラミング言語が異なるというだけでなく、異なるプログラミング言語を異なる方法で使用することでもあります。たとえば、C と C++ は似たようなプログラミング言語ですが、C プログラムはメモリのいくつかの大きなブロックを割り当てる傾向がありますが、C++ プログラムはメモリのより多くの小さなブロックを割り当てる傾向があります。

つまり、あなたの C 関数は 2 つの配列を取り (そしてそれらの長さを明示的に渡す必要があります)、Haskell では代わりにリストを使用します。(Haskell プログラムが決して配列を使用しないと言っているわけではありません。C プログラムが決してリストを使用しないというのは正しくないのと同じように、C プログラムは配列を使用する傾向があり、Haskell プログラムはリストを使用する傾向があるということです。)

showSpaced :: Show a => a -> String
showSpaced x = " " ++ show x ++ " "

あなたの C 関数は を呼び出しますprintf()。これは、出力をフォーマットして stdout に送信しますが、これらは別々に行います。 showSpacedに渡すことができるすべての値で動作しますshow。

union :: Ord a => [a] -> [a] -> [a]
union xs          []          = xs
union []          ys          = ys
union xs0@(x:xs1) ys0@(y:ys1) = case x `compare` y of
    LT -> x : union xs1 ys0
    GT -> y : union xs0 ys1
    EQ -> y : union xs1 ys1

このunion関数は、基礎となる要素を比較できることのみを必要とします。2 つのリストは、互いに同じタイプでなければなりません。ループの代わりに再帰を使用していること、および配列の代わりにリストを使用することで、配列インデックスを追跡する必要がないことに気付くでしょう。

それ自体に3 つの方程式を与えることによって、および式とともに、パターン マッチングを使用します。Haskell ではパターン マッチングが重要です。それを説明するチュートリアルを見つけてください。unioncase

printUnion :: (Ord a, Show a) => [a] -> [a] -> IO ()
printUnion xs ys = mapM_ (putStr . showSpaced) (union xs ys)

それで、printUnionすべてをまとめました。リスト要素はOrd( を呼び出せるようにunion) とShow( を呼び出せるように) 実装する必要がshowSpacedあるため、両方とも型シグネチャに表示されます。

C から来ているので、中間リストを作成する効率について心配するかもしれません。そうではありません: オプティマイザはすべてを 1 つのループに融合します。

于 2012-11-20T10:32:34.147 に答える