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 函数需要两个数组（并且必须明确地传递它们的长度），但在 Haskell 中我们将使用列表来代替。（这并不是说 Haskell 程序从不使用数组，正如 C 程序从不使用列表不是真的，只是 C 程序倾向于使用数组而 Haskell 程序倾向于使用列表。）

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

您的 C 函数调用printf()，它们都格式化输出并将其发送到标准输出，但我们将分别处理这些事情。 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功能只要求可以比较底层元素。这两个列表必须具有相同的类型。您会注意到我们使用递归而不是循环，并且通过使用列表而不是数组，我们不必跟踪数组索引。

我们使用模式匹配，既给union自己三个方程，也给case表达式。模式匹配在 Haskell 中很重要：给自己找一个解释它的教程。

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

所以printUnion我们把它们放在一起。列表元素需要实现Ord（所以我们可以调用union）和Show（所以我们可以调用showSpaced），所以它们都出现在类型签名中。

当您来自 C 语言时，您可能会担心建立中间列表的效率。不要这样：优化器会将所有内容融合到一个循环中。

于 2012-11-20T10:32:34.147 回答