08 July, 2014 by Denise << functional-programming >>

Iterative to Functional Recursion

So I'm working through a book called 'Functional Programming in Scala' and one of the exercises was to implement a recursive method for checking whether an array is sorted. The signature given was:

def isSorted[A](as: Array[A], gt: (A,A) => Boolean): Boolean

My first attempt looked like this:


 def isSorted[A](as: Array[A], gt: (A,A) => Boolean): Boolean = {

    def loop(index: Int): Boolean = {
      if (index >= (as.length - 1)) true
      else if (gt(as(index), as(index + 1))) loop(index + 1)
      else false
    }
    loop(0)
  }
  

but the array indexing was bothering me and I thought there must be a 'more functional' way. So I asked for a code review and was told that using a list might help, I reimplemented it as follows:


      def isSorted2[A](as: Array[A], gt: (A,A) => Boolean): Boolean = {

    def loop(as: Array[A]): Boolean = {
      if (as.length == 1 || as.length == 0) true
      else if (gt(as.head, as.tail.head)) false
      else loop(as.tail)
    }
    loop(as)
  }
  

I think this reads a lot cleaner, and I don't need to keep track of the index in my head anymore. These imperative ways of thinking are hard to break though!