Procedure Subsets(list):
    End_val = 2 ^ length of list
    For i from 0 to End_val (inclusive):
        Current_subset = the empty list
        For each bit b in i indexed by j:
            If b is 1:
                Add the jth element of list into Current_subset.
        Pause execution, providing Current_subset
            

Procedure powerset(list):
    If list is empty: Pause execution, providing the empty list
    Otherwise:
        Let v = the first value in the list
        And s = the iterator from powerset(rest of the list)
        For each value ss in s:
            Pause execution, providing v appended to ss.
            Pause execution, providing ss.
            

; When a value is delayed, it is stored in a function.
(define-syntax delay (syntax-rules ()
  ((delay val) (lambda () val))))

; Forcing it is a function call...
(define-syntax force (syntax-rules ()
  ((force val) (val))))

; Constructing a list is as above.
(define-syntax lazy-cons (syntax-rules ()
  ((lazy-cons x y) (cons x (lambda () y)))))

(define (lazy-car seq) (car seq)) ; Get the value
(define (lazy-cdr seq) (force (cdr seq))) ; Get the rest of the list
; The rest of the list is forced so that the current value is
; always computed and accessible immediately.

; Nerdy note: CAR and CDR are IBM Assembly directives that handle a
; cons cell. A cons has a Content Address Register and a
; Content Dereference Register. These are nicknames for a pointer to
; the current (car) and the rest of the list (cdr). You can find
; these in NASA's (ie. Margaret Hamilton's) 1960s assembly code.

; return whether anything satisfied a predicate
(define (any pred ls)
  (if (null? ls) #f
    (or (pred (car ls)) (any pred (cdr ls)))))

; This applies a function over each aligned value of iterators.
; If I1 and I2 are iterators of integers, (lazy-map + I1 I2) is an
; iterator through the component-wise sum.
(define (lazy-map fn . seqs) ; seqs is a list of iterators.
  (if (any null? seqs) '()   ; on the first empty iterator, stop.
      (lazy-cons (apply fn (map lazy-car seqs))
                 (apply lazy-map (cons fn (map lazy-cdr seqs))))))

(define (list-of-stream st)
  (if (null? st) '()
    (cons (lazy-car st) (list-of-stream (lazy-cdr st)))))

; An iterator that takes values from an iterator while a condition is
; true. Pred is a function that provided a sequence value, returns
; a boolean.
(define (take-while pred seq)
  (if (pred (lazy-car seq))
    (lazy-cons (lazy-car seq) (take-while pred (lazy-cdr seq)))
    '()))

;A few cool examples
;An infinite sequence of 1's
(define ones (lazy-cons 1 ones))

;The natural numbers
(define numbers (lazy-cons 1 (lazy-map + ones numbers)))

;Fibonacci
(define fibonacci (lazy-cons 0 (lazy-cons 1
                    (lazy-map + fibonacci
                                (lazy-cdr fibonacci)))))

; HERE IS THE SUBSETS IMPLEMENTATION
; Get all the values of a list based on an integer.
; If the i-th bit is 1, the i-th value is included.
(define (subsets-by-int lis int)
  (define (loop acc ind l)
    (if (= 0 ind) acc
      (loop (if (= 1 (remainder ind 2))
              (cons (car l) acc)
              acc)
            (floor (/ ind 2)) (cdr l))))
  (if (number? int) (loop '() int lis) '()))

; Generates all the subsets of a list “lis”.
; The empty subset is last, included as the empty-list flag
; that terminates the iterator.
(define (subsets lis)
  (let ((ln (expt 2 (length lis))))
    (lazy-map (lambda (i) (subsets-by-int lis i))
              (take-while (lambda (x) (< x ln)) numbers))))

; Recursion is more canonical. Below is an alternate approach.

; Concatenate a list of lazy sequences (in order).
(define (concat-streams . seqs)
  (cond ((null? seqs) '())
        ((null? (cdr seqs)) (car seqs))
        ((null? (car seqs)) (apply concat-streams (cdr seqs)))
        (else (lazy-cons (lazy-car (car seqs))
                (apply concat-streams
                       (cons (lazy-cdr (car seqs))
                             (cdr seqs)))))))

; More canonical lazy powerset.
(define (powerset ls)
  (if (null? ls) (lazy-cons '() '())
    (let ((h (car ls)) (ss (powerset (cdr ls))))
      (concat-streams (lazy-map (lambda (s) (cons h s)) ss) ss))))
            

(ns subset.core)

(defn subset-by-int [lis i]
  "Returns the subset where the i-th element is returned if
   the i-th bit is 1."
  (loop [acc '() v i l lis] ; this is the same as the Scheme thing.
    (if (= v 0) acc
      (recur (if (= 1 (mod v 2)) (conj acc (first l)) acc)
             (int (/ v 2))
             (rest l)))))

(defn subsets [s]
  "Returns all the subsets of s."
  (map #(subset-by-int s %) (->> s count (Math/pow 2) range)))

(defn powerset [s]
  "More canonical powerset."
  (if (empty? s) '(())
  (let [ss (-> s rest powerset)]
    (concat (map #(conj % (first s)) ss) ss))))
            

subset_of_int :: [a] -> Integer -> [a]
subset_of_int v 0 = []
subset_of_int (x:xs) i
              | i `mod` 2 == 0 = subset_of_int xs (i `quot` 2)
              | otherwise      = x : (subset_of_int xs (i `quot` 2))

subsets :: [a] -> [[a]]
subsets xs = map (subset_of_int xs) [0.. (2^(length xs)) - 1]

-- This is the alternative algorithm, but Haskell doesn't mind...
-- This will be lazy too!
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (x:xs) = (map (x:) ps) ++ ps
  where ps = powerset xs
            

open List;;

(*Ocaml is strongly typed. This is a generic lazy list.*)
type 'a stream = Nil | LazyList of 'a * (unit -> 'a stream)

let rec range st en = if st == en then Nil
                      else  LazyList (st, fun () ->
                                             range (st + 1) en);;

(*Unfortunately, variable number of arguments are poorly supported.*)
let rec map_str fn seq =
    match seq with
    | Nil -> Nil
    | LazyList (hd, tl) -> LazyList ((fn hd), fun () ->
                                                   map_str fn (tl ()))
;;

(*Converts a stream to a list (for finite ones).*)
let rec list_of_stream s =
    match s with
    | Nil -> []
    | LazyList (hd, tl) -> (hd :: list_of_stream (tl ()))
;;

(* This is the normal way to get subsets by the bit technique.*)
let rec subsets_of_int arr i =
    match i with
    | 0 -> []
    | x when x mod 2 == 0 -> subsets_of_int (tl arr) (x / 2)
    | y -> (hd arr) :: (subsets_of_int (tl arr) (y / 2))
;;

(* Gets all the subsets.*)
let subsets arr =
    let en = (truncate ((float (length arr)) ** 2. -. 1.)) in
        map_str (subsets_of_int arr) (range 0 en)
;;

(*Concatenates two streams into a lazy stream.*)
let rec concat_str st1 st2 =
    match st1 with
    | Nil -> st2
    | LazyList (h, t) -> LazyList (h, fun () -> concat_str (t ()) st2)
;;

(*The more naturally recursive powerset builder.*)
let rec powerset arr =
    match arr with
    | [] -> LazyList ([], fun () -> Nil)
    | (h :: t) -> let sm = powerset t in
                         concat_str (map_str (fun (s) -> h::s) sm) sm
;;

            

#This object is an iterator. It can be stepped through using a
#for-loop.
class SubsetIter:
    def __init__(self, data):
        self.data = data
        self.it = 0
        self.mx = 2 ** len(data)
    def __iter__(self):
        return self
    def __next__(self): #called "next" in py2
        if self.mx == self.it:
            raise StopIteration()
        else:
            i = self.it
            j = 0
            acc = []
            while i > 0:
                if i % 2 == 1:
                    acc.append(self.data[j])
                i //= 2 #py2 equivalent: i = int(i / 2)
                j += 1
        self.it += 1
        return acc

#This is not the most canonical. But it works.
def powerset(s):
    if len(s) == 0:
        yield []
    else:
        h, *t = s #use "h, t = s[0], s[1:]" in py2
        for i in powerset(t):
            yield i
            yield i + [h]
        

using System;
using System.Collections.Generic;
using System.Linq;

class MainClass {
    public static IEnumerable<List<T>> Subsets<T>(IList<T> vals){
        var acc = new List();
        foreach(int i in Enumerable.Range(0, (int) Math.Pow(2, vals.Count()) - 1)){
            for(int j = i, k = 0; j > 0; j /= 2, k++){
                if(j % 2 == 1)
                    acc.Add(vals[k]);
            }
            yield return acc;
            acc = new List();
        }
    }

    //Recursion is not canonical... but cool. This is slow too.
    public static IEnumerable<List<T>> Powerset<T>(IEnumerable<T> vals){
        if(!vals.Any())
            yield return new List();
        else{
            T tmp = vals.ElementAt(0);
            foreach(var t in powerset(vals.Skip(1))){
                yield return t;
                var l = t.ToList();
                l.Add(tmp);
                yield return l;
            }
        }
    }
}
        

//The lack of type information is a little sad.
var LazyList = function(head, rest){
    this.head = head;
    this.rest = rest;
};

//Infinite ones as in Scheme.
var ones = new LazyList(1, function(){return ones;});

var map = function(fn, lists){
    if(lists.some(function(l){return l === null}))
        return null;

    var hd = function(l){return l.head;};
    var recurse = function(){
        return map(fn, lists.map(function(v){
            return v.rest();
        }));
    };
    return new LazyList(fn.apply(null, lists.map(hd)), recurse);
};

var toArray = function(lis){
    var acc = [];
    while(lis !== null && lis !== undefined){
        acc.push(lis.head);
        lis = lis.rest();
    }
    return acc;
}

var ints = new LazyList(1, function(){
    return map(function(r, l){
        return r + l;
    }, [ones, ints]);
});

var takeN = function(lis, n){
    if(n === 0) return null;
    return new LazyList(lis.head, function(){
        return takeN(lis.rest(), n - 1);
    });
};

var getSubset = function(val, lis){
    var j = 0;
    var acc = [];
    for(var i = val; i > 0; i = Math.floor(i / 2)){
        if(i % 2 === 1) acc.push(lis[j]);
        j++;
    }
    return acc;
};

//Normal subsets impl
var subsets = function(l){
    return map(function(v){
        return getSubset(v, l);
    }, [takeN(ints, Math.pow(2, l.length))]);
};

var concat = function(lists){
    if(lists.length === 0)
        return null;
    else if(lists.length === 1)
        return lists[0];
    else if(lists[0] === null || lists[0] === undefined)
        return concat(lists.slice(1));
    else{
        var t = lists[0].head;
        lists[0] = lists[0].rest();
        return new LazyList(t, function(){
            return concat(lists);
        });
    }
};

//Recursion!
var powerset = function(l){
    if(l.length === 0){
        return new LazyList([], function(){
            return null;
        });
    }else{
        var v = l[0];
        var r = powerset(l.slice(1));
        return concat([r, map(function(vv){
            return vv.concat([v]);
        }, [r])]);
    }
};
        

struct Subsets<A>{
    counter: usize,
    data: Vec<A>
}

impl<A> Subsets<A>{
    fn new(data: Vec<A>) -> Subsets<A> {
        Subsets{
            counter: 0,
            data: data
        }
    }
}

impl<A> Iterator for Subsets<A>
where A: Clone{
    type Item = Vec<A>;
    fn next(&mut self) -> Option<Vec<A>>{
        if self.counter >= 2_usize.pow(self.data.len() as u32) {
            Option::None
        }else{
            let mut i = self.counter;
            let mut rv = Vec::new();
            let mut j = 0;
            while i > 0 {
                if i % 2 == 1 {
                    rv.push(self.data[j].clone());
                }
                i = i / 2;
                j += 1;
            }
            self.counter += 1;
            Option::Some(rv)
        }
    }
}
        

use std::rc::Rc;

enum Stream<T> {
    Data {
        value: T,
        next: Rc<dyn Fn() -> Stream<T>>,
    },
    Nil,
}

impl<T: Clone> Clone for Stream<T> {
    fn clone(&self) -> Self {
        match self {
            Stream::Nil => Stream::Nil,
            Stream::Data { value, next } => Stream::Data {
                value: value.clone(),
                next: next.clone(),
            },
        }
    }
}

fn map<A: 'static, B: 'static>(stream: Stream<A>, func: Rc<dyn Fn(A) -> B>) -> Stream<B> {
    match stream {
        Stream::Nil => Stream::Nil,
        Stream::Data { value, next } => Stream::Data {
            value: func(value),
            next: Rc::new(move || map(next(), func.clone())),
        },
    }
}

fn concat<A: 'static + Clone>(stream1: Stream<A>, stream2: Stream<A>) -> Stream<A> {
    match stream1 {
        Stream::Nil => stream2,
        Stream::Data { value, next } => Stream::Data {
            value: value.clone(),
            next: Rc::new(move || concat(next(), stream2.clone())),
        },
    }
}


fn singleton_stream<A>(a: A) -> Stream<A> {
    Stream::Data {
        value: a,
        next: Rc::new(|| Stream::Nil),
    }
}


fn subsets<A: 'static + Clone>(stream: Stream<A>) -> Stream<Stream<A>> {
    match stream {
        Stream::Nil => singleton_stream(Stream::Nil),
        Stream::Data { value, next } => {
            let others = subsets(next());
            concat(
                others.clone(),
                map(others, Rc::new(move |st| concat(singleton_stream(value.clone()), st))),
            )
        }
    }
}
        

nextSubset :: [Bool] -> [Bool]
nextSubset []         = [True]
nextSubset (True:xs)  = False:(nextSubset xs)
nextSubset (False:xs) = True:xs

subsets :: [a] -> [[a]]
subsets xs = map (map fst . filter snd
                          . zip xs)
                 $ iterate nextSubset []

finiteSubsets :: [a] -> [[a]]
finiteSubsets xs = take (2 ^ (length xs)) $ subsets xs
        

fn filter_map<A: 'static, B: 'static>(
    stream: Stream<A>,
    func: Rc<dyn Fn(A) -> Option<B>>,
) -> Stream<B> {
    match stream {
        Stream::Nil => Stream::Nil,
        Stream::Data { value, next } => match func(value) {
            Option::Some(val) => Stream::Data {
                value: val,
                next: Rc::new(move || filter_map(next(), func.clone())),
            },
            Option::None => filter_map(next(), func.clone()),
        },
    }
}

fn zip_streams<A: 'static, B: 'static>(left: Stream<A>, right: Stream<B>) -> Stream<(A, B)> {
    match left {
        Stream::Nil => Stream::Nil,
        Stream::Data {
            value: lv,
            next: ln,
        } => match right {
            Stream::Nil => Stream::Nil,
            Stream::Data {
                value: rv,
                next: rn,
            } => Stream::Data {
                value: (lv, rv),
                next: Rc::new(move || zip_streams(ln(), rn())),
            },
        },
    }
}

fn iterate_fn_stream<T: 'static + Clone>(initial: T, update: Rc<dyn Fn(T) -> T>) -> Stream<T> {
    Stream::Data {
        value: initial.clone(),
        next: Rc::new(move || iterate_fn_stream(update(initial.clone()), update.clone())),
    }
}
            

fn increment_infinite_binary_num(prev: Stream<bool>) -> Stream<bool> {
    match prev {
        Stream::Nil => singleton_stream(true),
        Stream::Data { value: true, next } => concat(
            singleton_stream(false),
            increment_infinite_binary_num(next()),
        ),
        Stream::Data { value: false, next } => concat(singleton_stream(true), next()),
    }
}

fn large_finite_subsets<A: 'static + Clone>(set: Stream<A>) -> Stream<Stream<A>> {
    let nats = iterate_fn_stream(Stream::Nil, Rc::new(increment_infinite_binary_num));
    map(
        nats,
        Rc::new(move |nat| {
            filter_map(
                zip_streams(set.clone(), nat),
                Rc::new(|(x, n)| if n { Option::Some(x) } else { Option::None }),
            )
        }),
    )
}