CODEWITHSUNDEEP
algorithmhaskellpermutationsml
asaak
asaak

Reputation: 23

Translate Haskell code into Standard ML (combinations with repetition)

I am writing a code for the permutation with repetition for n elements drawn from choice of k values. So the cardinality of my resulting set should have k^n elements. In Haskell, it is fairly easy. For example, one can just write:

import Control.Monad (replicateM)

main = mapM_ print (replicateM 2 [1,2,3])

then you will get a list as:

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

But on Standard ML, I don't know how to do.

I tried this:

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)

But the list is not complete and I don't know why....

Is there an analog coding as the one in Haskell that does the same thing? Or how should I fix my sml code?

Any help is appreciated!

Upvotes: 2

Views: 389

Answers (1)

Will Ness
Will Ness

Reputation: 71074

Just transform the monadic code:

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)

Now you can translate this to ML.

Upvotes: 1

Related Questions