function to return index of largest neighbor

Question

F# function

Problem:

given a list of items e.g.:

["5";"10";"2";"53";"4"]

and a Search Index, I require a function such that it compares the current given index against its neighbor, returning the largest index

Example:

• Given Index 1 will return Index value 2 (because 10 is greater than 5).
• Given Index 4 will return Index 4 (because 53 is greater than 4)

Currently this is my function. It does not compile:

let GetMaxNode (x:Array) Idx = if x.[Idx] > x.[Idx+1] then  Idx else If  x.[Idx] < x.[Idx+1] then  Idx+1

The errors I'm getting for all the x' are:

The field, constructor or member 'Item' is not defined (FS0039)

And also the second If:

The value or constructor 'If' is not defined (FS0039)

I suspect I'm still thinking in a procedural way, I was thinking about using pattern matching, however I was not confident enough with the syntax to try it.

Please can you also explain the answer as well, as I'm trying to learn F#, just the solution will not help me much.

Answer 1

Here's some code based on yours:

let GetMaxNode (x:_[]) idx = 
    if x.[idx] > x.[idx+1] then  
        idx 
    elif x.[idx] < x.[idx+1] then  
        idx+1 
    else
        idx // same, return this one

The main changes are

• to declare an array type, say <typename> []. In this case, we don't care about the type, so I use _ as a "don't care, please go infer the right thing for me" type variable.
• "else if" is spelled elif in F#
• need an else case for if equal

Answer 2

It is difficult to write solution to your problem in a functional style, because your problem is defined in terms of indices - when using functional data structures, such as lists, you don't usually refer to the elements by their index.

A functional version of your question would be, for example, to create a list that contains true when the element at the current position is larger than the next one and false when it is smaller. For your data this would give:

let data = [ 5;     10;   2;     53;   4 ]
let res  = [ false; true; false; true; ] // no item to compare '4' with 

This can be solved quite nicely using a recursive function that walks through the list and pattern matching (because pattern matching works much better with functional lists than with arrays)

let rec getMaxNodes data = 
  match data with 
  // list has at least two elements and current is larger
  | current::next::other when current >= next ->
      // process the rest of the list
      let rest = (getMaxNodes (next::other))
      // return 'true' followed by recursively processed rest of the list
      true::rest
  // list has at least two elements and current is smaller
  | current::next::rest ->
      // same as the previous case, but we return false
      false::(getMaxNodes (next::rest))
  | _ -> 
      // one element (so we cannot compare it with the next one)
      // or empty list, so we return empty list
      []

getMaxNodes data

Answer 3

Here's the pattern matching version of Brian's answer.

let GetMaxNode (x:_[]) idx =
    match idx with
    | idx when x.[idx] > x.[idx+1] -> idx
    | idx when x.[idx] < x.[idx+1] -> idx + 1
    | idx -> idx // same, return this one

You may also see a syntax shortcut as you look at more F# code. The below code is functionally exactly the same as the above code.

let GetMaxNode (x:_[]) = function
    | idx when x.[idx] > x.[idx+1] -> idx
    | idx when x.[idx] < x.[idx+1] -> idx + 1
    | idx -> idx // same, return this one

Answer 4

Whenever you start talking about indices, you are best sticking with Arrays or ResizeArrays; F# lists are not well-suited for operations on indices since they are singly-linked head to tail. That being said, it is not too difficult to write this algorithm in a purely functional way by moving through the list using a recursive loop and keeping track of the current index and current element.

let find elements index =
    //a local tail-recursive function hides implementation details
    //(cur::tail) is a pattern match on the list, i is the current index position
    let rec loop (cur::tail) i =
        if i = index then //when the current index matches the search index
            if cur >= tail.Head then i //compare cur to tail.Head (which is next)
            else (i+1)
        else loop tail (i+1) //else continue
    loop elements 0 //the entry point of loop and our return value

Use a list of ints instead of strings to get the results you expect (since "10" is actually less than "5"):

> let x = [5;10;2;53;4];;
> find x 0;;
val it : int = 1
> find x 1;;
val it : int = 1
> find x 2;;
val it : int = 3
> find x 3;;
val it : int = 3