K out on N implementation - SML

Question

I was trying to implement k-out-of-N at SML so "pick(3,[1,2,3,4])" will return [[1,2,3],[1,3,4]...] (all the K-size picks out of N elements)

I used List.map which I figured it calls the function and apply it on each element.

Really can't figure out why when typing the input "pick(3,[1,2,3,4,5])" ,for example, it return an empty list.

My first thought was that it's because of the initial terms (choose (_,[]) = []) But changing it didn't work as well.

The signature is ok (val pick = fn : int * 'a list -> 'a list list).

fun pick (_,[]) = []
    | pick (0,_) = []
    | pick (n,hd::tl) =
      let
        val with_hd = List.map (fn x => hd::x) (pick(n-1,tl))
        val without_hd = pick(n,tl)
      in
      with_hd@without_hd
 end;

Answer 1

The problem is related to your suspicion – the base cases are incorrect in that they always produce the empty list, and mapping fn x => hd::x onto the empty list produces the empty list.

Picking zero elements from anything should succeed, and produce the empty list.
That is, pick (0, _) = [[]] — a list with one element, which is the empty list.

You also need to rearrange the cases since pick(n, []) succeeds for n = 0 but not for any other n.

In summary,

fun pick (0, _) = [[]]
  | pick (_, []) = []

with the rest of the function exactly as before.