Lists. They are the butter and bread of functional programming and possibly my favorite data structure ever.

This is how they are defined in the standard library:

union List a = empty | a :: List a

It's a trivial linked list, which means you can't access elements randomly, you always have to traverse them in order.

As you can see, lists can either be empty or have a first element and a rest of the list. Using the :: constructor repeatedly allows for creating longer and longer lists:

empty
1 :: empty
1 :: 2 :: empty
1 :: 2 :: 3 :: 4 :: 5 :: 6 :: 7 :: empty

And using recursion, one can even create infinite ones:

func one-two-three : List Int = 1 :: 2 :: 3 :: one-two-three

This doesn't enter an infinite loop because Funky is a lazily evaluated language.

Of course, typing colons all the time would be tiresome, and so Funky provides a nice syntax sugar with the usual square brackets.

["a", "b", "c", "d"]

Expands to:

"a" :: "b" :: "c" :: "d" :: empty

Well, actually... since the String type is defined as List Char, the string literals must also get expanded to colons, right? Yep, so the full expansion actually is this monstrosity:

('a' :: empty) :: ('b' :: empty) :: ('c' :: empty) :: ('d' :: empty) :: empty

After seeing this, I'm sure you're way more grateful for all the string and list syntax sugar than you've ever been before.

With lists comes the legacy of tools, perfected and sharpened for long generations.

The most basic and important ones are empty?, first! and rest!:

$ funkycmd -types
> empty?
List a -> Bool
> first!
List a -> a
> rest!
List a -> List a

The REPL will print more version of the empty? function, but the one listed here is the important one. The functions are simple: empty? tells if a list is empty, first! returns the first element of the list, and rest! cuts off the first element and returns what remains. All other list functions can be implemented in terms of these three (or in terms of switch/case).

Details. Functions first! and rest! have the '!' symbol in them because they can crash: they crash when the list is empty. They have their non-crashing versions called first and rest that return a Maybe. We'll learn more about maybes in another part.

Now, let me (re)introduce you to map and filter.

The function map simply applies a function to all of the elements of the list:

map sqrt [1.0, 4.0, 9.0, 16.0]  # => [1.0, 2.0, 3.0, 4.0]
map (* 3) [5, 1, 3, 2]          # => [15, 3, 9, 6]

The function filter takes a predicate and filters out all the elements that don't satisfy it:

filter (< 5) [9, 3, 4, 7, 5, 10, 1]  # => [3, 4, 1]
filter even? [1, 2, 3, 4, 5, 6, 7]   # => [2, 4, 6]

Then there is a nice zip function which "zips" two lists with some binary function (it's like zipWith from Haskell; the zip function from Haskell can be done with zip pair in Funky). It takes the first elements from both lists, applies the function to them, and goes on, like this:

zip (*) [1, 2, 3] [2, 3, 4]           # => [2, 6, 12]
zip (++) ["he", "wo"] ["llo", "rld"]  # => ["hello", "world"]

The zip function enables this ultra cool hipster Fibonacci one-liner:

func fibs : List Int =
    0 :: 1 :: zip (+) fibs (rest! fibs)

There are more list functions, like fold< and fold> (those are same as foldr and foldl' in Haskell), but we'll not give them too much attention, you can try them out on your own. For example, here's how you'd sum a list of numbers with fold>:

fold> (+) 0 (range 1 15)  # => 120

Other list functions include reverse, take, drop, any, all, iterate, and so on. The usual ones.

Now, all that stuff is cool, but if we can't print a list, it's all useless, right? Well, this leads us to a very interesting function from the standard library called for. Yes, the name is intentionally chosen to match the name of the old imperative concept - the for-loop. Of course, loops in imperative programming rely on the mutation of the loop variables. We can't do that in functional programming, but our for-loop will be just as ergonomic as the imperative one.

So, what's the type of this mighty for function?

$ funkycmd -types
> for
List a -> (a -> c -> c) -> c -> c

It takes three arguments. Here's what they are and how you can think about them:

• List (type List a). This is the list of things we want to loop over.
• Body (type a -> c -> c). You can think of this as something we want to "do" for each element.
• Next (type c). This will get "done" after getting over with all the elements.

Obviously, the descriptions above are rather inaccurate. We can't do anything, we can only make values and data structures.

The best way to explain what for does is to start with an example. So, let's print a list:

func main : IO =
    for ["A", "B", "C"]
        println;
    quit

Oh man, that looks imperative! Does it even work?

$ funkycmd for.fn
A
B
C

It does!

We've passed ["A", "B", "C"] as the list to for. Then we passed println as the body. The println function perfectly fits the required type of the argument: a -> c -> c, specialized to String -> IO -> IO in our case. Because println takes and returns IO, the last argument to for must be an IO. So we passed quit.

As we already know, println constructs the IO data structure and the same goes for quit. So for is in fact just applying functions in some way. What could that way be?

First of all, if we pass an empty list, we just get the next back.

for [] body next  # => next

If we pass a single element list, we get the body applied to the element and the next:

for [a] body next  # => body a next

What about a two element list? Well, that looks like this:

for [a, b] body next  # => body a (body b next)

Three elements?

for [a, b, c] body next  # => body a (body b (body c next))

In other words:

for (x :: xs) body next

is equivalent to:

body x (for xs body next)

which can be easily rewritten to:

body x;
for xs body;
next

The working of for can also be seen in the following diagram:

Note. Yes, for is exactly the same function as fold<, except with a different order of arguments.

Knowing this, it's easy to see that our list printing program:

func main : IO =
    for ["A", "B", "C"]
        println;
    quit

basically expands to this:

func main : IO =
    println "A";
    println "B";
    println "C";
    quit

It's all very clear now!

The next argument doesn't have to be just a quit. It can be more complex:

func main : IO =
    for ["A", "B", "C"]
        println;
    println "Done!";
    quit

or even another for loop:

func main : IO =
    for ["A", "B", "C"]
        println;
    println "First half!";
    for ["D", "E", "F"]
        println;
    println "Second half!";
    quit

With the semicolon, we can get much of the convenient code structuring of imperative programming. Without monads!

If we change the list to a list of numbers, the scheme no longer works:

func main : IO =
    for (range 1 5)
        println;
    quit

Details. The range function takes the lower and the upper bound and evaluates to a list of all integers in between, including the bounds.

Trying to run this gives us an error:

$ funkycmd for.fn
for.fn:3:9: type-checking error

That's quite obvious. We have a list of Ints, but println takes a String. This can be fixed by composing println with string, which converts Ints (and is overloaded for other types) to Strings:

func main : IO =
    for (range 1 5)
        (println . string);
    quit

This time, it works!

$ funkycmd for.fn
1
2
3
4
5

So far, we've only seen a simple function or a composition of two functions as the body argument to for. What if we want to have a more elaborate loop body? Say a two printlns for the start.

You might be tempted to try this:

func main : IO =
    for (range 1 5)
        (print "#"; println);
    quit

But that just doesn't work. We can't pass println as the second argument to print, that's just nonsense, it expects an IO, not String -> IO -> IO.

Here's what we need to do. Let's start with the simple for-loop on strings.

func main : IO =
    for ["A", "B", "C"]
        println;
    quit

Instead of just passing the function println itself, let's make it a lambda:

func main : IO =
    for ["A", "B", "C"] (
        \s \next
        println s;
        next
    );
    quit

The body of the for loop takes two arguments: the element of type String, and the continuation of type IO. We pass both of these to the println function, recreating the original, short for-loop. This doesn't at all change the behavior of the program.

However, as you can surely see, it's very straightforward to add more "statements" to the body:

func main : IO =
    for ["A", "B", "C"] (
        \s \next
        print "- ";
        println s;
        next
    );
    quit

Let's run it!

$ funkycmd body.fn
- A
- B
- C

We can even add scans to the loop!

func main : IO =
    print "What's the number of questions? ";
    scanln \n-str
    let (int n-str) \n
    for (range 1 n) (
        \i \next
        print ("Your question #" ++ string i ++ ": ");
        scanln \question
        println "The answer: IDK.";
        next
    );
    quit

Let's run this funny program:

$ funkycmd questions.fn
What's the number of questions? 3           
Your question #1: What's your name?
The answer: IDK.
Your question #2: How are you doing IDK?
The answer: IDK.
Your question #3: Do you know anything?
The answer: IDK.

And you can even nest loops! Here's a program that prints out the small multiplications table... in a non-tabular form, but that's okay.

func main : IO =
    for (range 1 10) (
        \x \next
        for (range 1 10) (
            \y \next
            print (string x);
            print " x ";
            print (string y);
            print " = ";
            println (string (x * y));
            next
        );
        next
    );
    quit

Note. Those multiple prints aren't necessary, it could've all been done with one long string concatenation. Splitting it into multiple lines just makes it clearer. This problem will go away once there is a better way to format strings.

And run it!

$ funkycmd multiplications.fn
...
5 x 7 = 35
5 x 8 = 40
5 x 9 = 45
5 x 10 = 50
6 x 1 = 6
6 x 2 = 12
6 x 3 = 18
6 x 4 = 24
6 x 5 = 30
6 x 6 = 36
6 x 7 = 42
6 x 8 = 48
6 x 9 = 54
6 x 10 = 60
7 x 1 = 7
7 x 2 = 14
7 x 3 = 21
7 x 4 = 28
7 x 5 = 35
...

It works! I didn't show the whole output, because that's too large, but you get the idea.

That's it for this part, in the next part, we'll learn more list tricks!