I am trying to learn FP using the Manning MEAP boo...

# arrow

[pajatopmr]

I am trying to learn FP using the Manning MEAP book Functional Programming in Kotlin. There is one exercise for which no answer is provided that I have a solution but it kind of seems yucky to me. How might an experienced FP Kotlin developer solve this:

[CLOVIS]

You didn't use foldRight correctly: your length function should be:

fun <A> length(xs: List<A>) = foldRight(xs) { e, acc -> when(e) {
  is Nil -> 1
  is Cons -> 1 + acc
}}

The point of using fold is to not have to handle recursion yourself.

[CLOVIS]

How is your .tail implemented?

[raulraja]

@pajatopmr assuming foldRight is already defined I think length can be just defined as:

fun <A> List<A>.length(): Int =
    foldRight(0) { _, acc -> 1 + acc }

May have to change the arg order if in your case you are declaring these as top level functions without a receiver:

fun <A> length(xs: List<A>): Int =
    foldRight(xs, 0) { _, acc -> 1 + acc }

Since fold will reduce all elements of the list into a final summary value List<A> -> B let’s call it B the length of the list can be determined by making B be an Int and adding the start counter at 0.
In all folds first you provide or have to deal with the empty identity but pattern matching and folding it’s the same. If you already have foldRight defined, then most other operations can be expressed in terms of it.

When we code with exhaustive pattern matching or when we fold we are effectively evaluating all possible cases in which an algebraic data type (sealed hierarchy) can be on. For example List can be Cons or Nil in your case. When you fold, the operation asks you to provide the empty identity. We provide 0 as that empty identity for the Int monoid which is what we want to return if the list is Nil. Then we provide a function that adds one to the acc to count how many elements there are. This function is is the associative operation needed for the list structure to be turned into a single final value.

I think this exercise tries to teach you:
1. Data structures can be represented algebraically with recursive sealed data types (side note, not efficient)
2. Pattern matching in all cases is the same as fold, fold is in fact implemented as such.
3. All terminal operations of any data structures whether it’s a List, IO or whatever are just specialisations of folds including length.
4. All of these terminal operations involve whether implicit or explicitly the notion of an empty identity, in the case of length 0 which is what it’s returned if the structure is empty

[raulraja]

If you like the topic once you get through this and you have’t already ventured you may be interested in Monoids, they are key to understand how you can reason about this kind of aggregate style operations and also Recursion schemes as folding is just one of them.

[pajatopmr]

@CLOVIS @raulraja Thank you both for your replies. Of the three solutions, Raul's second resonates for me the most at this point. It is concise, clear and passes the test, exactly what I was looking for.
I probably should have included the author's set up code, which is:

sealed class List<out A> {
    companion object {
        fun <A> of(vararg aa: A): List<A> {
            val tail = aa.sliceArray(1 until aa.size)
            return if (aa.isEmpty()) Nil else Cons(aa[0], of(*tail))
        }

        fun <A> empty(): List<A> = Nil
    }
}

object Nil : List<Nothing>() {
    override fun toString(): String = "Nil"
}

data class Cons<out A>(
    val head: A,
    val tail: List<A>
) : List<A>()

Monoids is coming up soon.

[pajatopmr]

btw, the book does mention Arrow a few times and is the most recent that I could find that deals explicitly with FP and Kotlin. Alternative recommendations that satisfy those two constraints would be great as the book has lots of errors and does not seem to be getting a lot of love from the author/publisher (few and slow updates).

[pajatopmr]

btw, Raul, if you keep answering questions like you've been doing for me, that in itself would be a book well worth reading (and buying). 🙂 Much appreciated.

[julian]

@pajatopmr This is the best book for Kotlin and FP. I can say this with confidence because I've looked into probably every book on FP (with or without Kotlin) available for working developers. It's still a MEAP, so be patient regarding errors and updates. Having started the book when it was first introduced, I assure you there's progress being made and the author is very invested in the project, which is nearing conclusion 🚀. He's on this channel, actually, and is very responsive. Also, there's a channel just for the book, that I started - #fp-in-kotlin. However, not much action so far in there besides me.

[pajatopmr]

Wow, that is awesome! So good to hear. The book is really a good one for me on three fronts: learning FP, teaching me things about Kotlin I did not realize that I didn't know, and introducing a few Arrow tidbits.