首页 文章

将Haskell代码转换为标准ML（重复组合）

提问于
浏览 次
2

我正在编写一个代码，用于重复排列从k值中选择的n个元素 . 所以我得到的集合的基数应该有k ^ n个元素 . 在Haskell中，它相当容易 . 例如，人们可以写：

import Control.Monad（replicateM）main = mapM_ print（replicateM 2 [1,2,3]）

然后你会得到一个列表：

[1,1] [1,2] [1,3] [2,1] [2,2] [2,3] [3,1] [3,2] [3,3]

但在标准ML上，我不知道该怎么做 .

我试过这个：

fun combs_with_rep（k，xxs）= case（k，xxs）of（0，）=> [[]]
|（，[]）=> []

|（k，x :: xs）=> List.map（fn ys => x :: ys）（combs_with_rep（（k-1），xxs））@ combs_with_rep（k，xs）

但列表不完整，我不知道为什么....

有没有像Haskell那样的模拟编码做同样的事情？或者我应该如何修复我的sml代码？

任何帮助表示赞赏！

algorithm haskell permutation sml

1 回答

  • 1

    只需转换monadic代码：

    rep_comb n xs  -- n times choose 1 elem from xs, repetition allowed
  = replicateM n xs 
  = sequence $ replicate n xs
  = foldr k (return []) $ replicate n xs
        where
          k m m' = do { x <- m; xs <- m'; return (x:xs) }
  = case n of 0 -> [[]] ;
              _ -> k xs (rep_comb (n-1) xs)
        where
          k m m' = m >>= (\x-> 
                   m' >>= (\xs ->  return (x:xs) ))
  = case n of 0 -> [[]] ;
              _ -> xs >>= (\y-> 
                   rep_comb (n-1) xs >>= (\ys -> [y:ys]))
  -- i.e.
  = case n of 0 -> [[]] ;
              _ -> [y:ys | y<- xs, ys<- rep_comb (n-1) xs]
  = case n of 0 -> [[]] ;
              _ -> concatMap  (\y-> map (y:) (rep_comb (n-1) xs))  xs
  -- or, in a different order
  = case n of 0 -> [[]] ;
              _ -> [y:ys | ys<- rep_comb (n-1) xs, y<- xs]
  = case n of 0 -> [[]] ;
              _ -> concatMap  (\ys-> map (:ys) xs)  (rep_comb (n-1) xs)

    现在你可以把它翻译成ML .

    回复于

相关问题