Powerset

This is an algorithm to compute a powerset. For example, given the set [1, 2, 3] the program should compute [[1, 2, 3], [1, 2], [1, 3], [2,3], [1], [2], [3], []]. The program is written in the Felix programming language.

fun find_seq[T] (k:size) (l:list[T]) : list[list[T]] =
  {
    return
      if k > len l
      then
        list[list[T]] () //There are no subsets of length k.
      elif k == 0uz
      then
        list[list[T]] (list[T] ()) //The empty set (the one subset of length zero).
      else
        match l with
          | Cons(?x, ?xs) => 
             join 
              (map (fun (l:list[T]):list[T]=>
                           (join (list[T] x) l)) (find_seq (k - 1) xs))
              (find_seq k xs)
        endmatch
      endif
    ;
  }
  
  fun power_set[T] (lst:list[T]):list[list[T]] =
  {
    fun loop[T] (k:size) (lst:list[T]) (acc:list[list[T]]):list[list[T]] =
    {
      return
        if k == size(-1) then acc
        else loop (k - 1) lst (join acc (find_seq k lst))
        endif
      ;  
    }
  
   return loop (len lst) lst (list[list[T]] ());
  }
  
  println$ str (power_set (list (1, 2, 3)));