https://kotlinlang.org logo
#functional
Title
# functional
j

Jakub Pi

04/23/2020, 3:39 PM
Both Joy of Kotlin and FP in Kotlin have exercises to implement foldRight using foldLeft. Joy of Kotlin has a solution using reverse:
Copy code
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):
Copy code
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?
j

Jakub Pi

04/23/2020, 4:55 PM
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.
r

raulraja

04/23/2020, 6:25 PM
people usually base foldRight on foldLeft because foldLeft usually is stack safe
🙂 1
j

Jakub Pi

05/03/2020, 8:33 PM
@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
Copy code
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)
}
🙈 1
6 Views