scalafunctional-programminglcm

FP LCM in scala in 1 line

I am trying to implement LCM in one line in Scala.

This is how I've implemented it with 2 functions:

def gcd(a: BigInt, b: BigInt):BigInt=if (b==0) a.abs else gcd(b, a%b)
def lcm(list: Seq[BigInt]):BigInt=list.foldLeft(BigInt(1))((a, b) => (a/gcd(a,b))*b)

How would you convert gcd into a lambda inside lcm?

Solution

  • You need a GCD calculation that isn't recursive.

    def lcm(list: Seq[BigInt]):BigInt=list.foldLeft(1:BigInt){(a,b) => b*a / Stream.iterate((a,b)){case (x,y) => (y, x%y)}.dropWhile(_._2 != 0).head._1.abs}

    (Here it is in a slightly more readable format.)

    def lcm(list: Seq[BigInt]):BigInt=list.foldLeft(1:BigInt){
  (a, b) => b * a /
  Stream.iterate((a,b)){case (x,y) => (y, x%y)}.dropWhile(_._2 != 0).head._1.abs
}