Both Joy of Kotlin and FP in Kotlin have exercises...

# functional

[Jakub Pi]

Both Joy of Kotlin and FP in Kotlin have exercises to implement foldRight using foldLeft. Joy of Kotlin has a solution using reverse:

fun <B> foldRightViaFoldLeft(identity: B, f: (A) -> (B) -> B): B =
        this.reverse().foldLeft(identity) { x -> { y -> f(y)(x) } }

FP in Kotlin is still in Early Access so the solutions aren't yet available on their github page. But this is what I came up with (using an identity function and composition):

fun <A, B> foldRight2(xs: List<A>, z: B, f: (A, B) -> B): B = foldLeft(xs, {y : B -> y}) { g, a -> {x : B -> f(a, g(x))}}(z)

I've basically used foldLeft to build up a function that will evaluate in the same order as an equivalent foldRight and then executed it with the original identity value. Is this close to the accepted solution or are there downsides to this approach?

[stojan]

this is what I came up with: https://github.com/LordRaydenMK/fpscala.kt/blob/9131afdc19299e645656d4aba0423d696cff8493/src/main/kotlin/chapter3/exercise3.13.kt#L3

[Jakub Pi]

Thanks, that's exactly what I was looking for. For some reason my more complicated solution is still easier for me to reason about. I don't think I've wrapped my head around the recursive definition of the accumulator quite yet. I'm sure there's already some special FP name to the construct I created.

[raulraja]

people usually base foldRight on foldLeft because foldLeft usually is stack safe

[raulraja]

but depending on the type there are specialized effitient impls https://github.com/JetBrains/kotlin/blob/master/libraries/stdlib/common/src/generated/_Collections.kt#L1642

[Jakub Pi]

@stojan Your solution evaluates the arguments in the wrong order. There is an appendix with the proper solution here: https://livebook.manning.com/book/functional-programming-in-kotlin/a-exercise-solutions/v-3/54

fun <A, B> foldLeftR(xs: List<A>, z: B, f: (B, A) -> B): B =
    foldRight(xs, { b: B -> b }, { a, g -> { b -> g(f(b, a)) } })(z)

fun <A, B> foldRightL(xs: List<A>, z: B, f: (A, B) -> B): B =
    foldLeft(xs, { b: B -> b }, { g, a -> { b -> g(f(a, b)) } })(z)

//expanded example
typealias Identity<B> = (B) -> B

fun <A, B> foldLeftRDemystified(
    ls: List<A>,
    acc: B,
    combiner: (B, A) -> B
): B {

    val identity: Identity<B> = { b: B -> b }

    val combinerDelayer: (A, Identity<B>) -> Identity<B> =
        { a: A, delayedExec: Identity<B> ->
            { b: B ->
                delayedExec(combiner(b, a))
            }
        }

    val chain: Identity<B> = foldRight(ls, identity, combinerDelayer)

    return chain(acc)
}