list.c

//
//  HASKELL FTW
//

typedef const int Int;
typedef const int Bool;

// data List a = Cons a (List a) | Nil
typedef const enum ListType { Nil, Cons } ListType;
typedef const struct List {
    ListType type;
    symtab * pair;
    const struct List * cons;
} List;

// printList = concat . map show
void
printList_ (List * list) {
    switch (list -> type) {
        case Nil:
            break;
        case Cons:
            if (list -> pair)
                printSym(list -> pair);
            printList_(list -> cons);
    }
}

void
printList (List * list) {
    printList_(list);
    printf("\n");
}


List *
allocList (ListType type, symtab * pair, List * cons) {

    List list = { type, pair, cons };
    void * alloc = malloc(sizeof(List));
    memcpy(alloc, &list , sizeof(List));
    List * p = alloc;

    return p;
}


void
destroyList (List * list) {
    switch (list -> type) {
        case Nil:
            free((void *)list);
            break;
        case Cons:
            if (list -> cons)
                destroyList(list -> cons);
            free((void *)list);
            break;
    }
}

List *
nil () {
    return allocList(Nil, NULL, NULL);
}

List *
cons (List * a, List * b) {
    List * n = allocList(Cons, a -> pair, b);
    return n;
}

// concatenate :: [a] -> [a] -> [a]
// concatenate [] list = list
// concatenate (x:xs) list = x : concatenate xs list
List *
concatenate (List * a, List * b) {
    if (a -> type == Nil) {
        return b;
    } else {
        return cons(a, concatenate(a -> cons, b));
    }
}

List *
filter (char * lexeme, List * list, Bool gte) {
    switch (list -> type) {
        case Nil:
            return nil();
            break;
        case Cons:
            if (gte) {
                if (strcmp(lexeme, list -> pair -> lexeme) <= 0) {
                    return cons(list, filter(lexeme, list -> cons, gte));
                } else {
                    return filter(lexeme, list -> cons, gte);
                }                
            } else {
                if (strcmp(lexeme, list -> pair -> lexeme) > 0) {
                    return cons(list, filter(lexeme, list -> cons, gte));
                } else {
                    return filter(lexeme, list -> cons, gte);
                }
            }
            break;
    }
}

// qsort :: Ord a => [a] -> [a]
// qsort [] = []
// qsort (x:xs) = qsort smaller ++ [x] ++ qsort larger
//     where   smaller = filter (< x) xs
//             larger = filter (>= x) xs
List *
quicksort (List * list) {
    switch (list -> type) {
        case Nil:
            return nil();
            break;
        case Cons:;
            List * smaller = filter(list -> pair -> lexeme, list -> cons, 0);
            List * larger = filter(list -> pair -> lexeme, list -> cons, 1);
            return concatenate(quicksort(smaller), cons(list, quicksort(larger)));
            break;
    }
}