I really miss return and break statements

General
1

I’m learning F#. I’m working through the advent of code problems. I pasted my day 6 solution below.

After completing 6 days of puzzles, I find I really miss break statements and early return statements that are in many other languages. In order to return from the while loop in walk, I had to invent the WalkResult type, and later call Option.get which may throw an exception if I got the logic wrong. Plus, about 10 lines of code ends up further indented in an else block. None of this would be necessary if F# provided an early return statement.

Also, in part1, I count characters the functional way using Array.sumBy and friends. In part2 I abandon that technique and use a mutable count and for loops. I find part2 much easier to read.

Are there better ways to do what I’m attempting to do?

open System.IO

let input = File.ReadAllLines("input.txt")

// Find the starting position
let mutable startPos = (-1, -1)
for row in 0..input.Length-1 do
    if (-1, -1) = startPos then
        let line = input[row]
        let i = line.IndexOf('^')
        if i >= 0 then
            startPos <- (row, i)

let rows = input.Length
let cols = input[0].Length

type WalkResult =
| Escaped
| InfiniteLoop

// Trace the path, leaving footprints of a, b, d, and h in lines.
// The least significant 4 bits of a, b, d, and h are distinct.
// a: 0001
// b: 0010
// d: 0100
// h: 1000
// The most significant 4 bits are all 0110.
let pathMask = uint8 0b01100000

let walk (lines: char array array) =
    let mutable step = (-1, 0, 'a')
    let mutable result = None
    let mutable pos = startPos
    while Option.isNone result do
        let (row, col) = pos
        let (i, j, c) = step

        // Calculate the new value for this space.
        let footPrint = lines[row][col]
        let footPrintByte = uint8 footPrint
        let newFootPrint =
            if pathMask &&& footPrintByte = pathMask then
                char (footPrintByte ||| (uint8 c))  // Merge with footprint
            else
                c  // Replace space with footprint.
        if footPrint = newFootPrint then
            result <- Some InfiniteLoop
        else
            lines[row][col] <- newFootPrint

            // Examine the next space.
            let (row, col) = (row + i, col + j)
            if row < 0 || row >= rows || col < 0 || col >= cols then
                result <- Some Escaped
            else if lines[row][col] = '#' then
                // Turn right 90 degrees.
                step <-
                    match step with
                    | (-1, 0, 'a') -> (0, 1, 'b')
                    | (0, 1, 'b') -> (1, 0, 'd')
                    | (1, 0, 'd') -> (0, -1, 'h')
                    | (0, -1, 'h') -> (-1, 0, 'a')
                    | bad -> failwith "Bad step"
            else
                pos <- (row, col) // Leave a footprint in the next space.
    Option.get result

let part1 =
    let lines = input |> Array.map (fun line -> line.ToCharArray())
    walk lines |> ignore

    // Count path.
    let isPathChar = fun (c: char) -> pathMask = ((uint8 c) &&& pathMask)
    let count =
        lines |> Array.sumBy (fun row -> 
            Array.filter isPathChar row |> Array.length)

    printfn "part1 %d" count

let part2 =
    let mutable count = 0
    for row in 0..rows-1 do
        for col in 0..cols-1 do
            let lines = input |> Array.map (fun line -> line.ToCharArray())
            lines[row][col] <- '#'
            if InfiniteLoop = walk lines then
                count <- count + 1
    
    printfn "part2 %d" count
2

Chat GPT helped me transform the code into something more idiomatic:

open System.IO

let input = File.ReadAllLines("input.txt")

// Find the starting position
let findStartPosition input =
    input
    |> Array.mapi (fun row (line: string) ->
        match line.IndexOf('^') with
        | i when i >= 0 -> Some (row, i)
        | _ -> None)
    |> Array.tryPick id
    |> Option.get

let startPos = findStartPosition input

let rows = input.Length
let cols = input[0].Length

type WalkResult =
    | Escaped
    | InfiniteLoop

// Constants for footprints
let pathMask = uint8 0b01100000

let turnRight (step: int * int * char) =
    match step with
    | (-1, 0, 'a') -> (0, 1, 'b')
    | (0, 1, 'b') -> (1, 0, 'd')
    | (1, 0, 'd') -> (0, -1, 'h')
    | (0, -1, 'h') -> (-1, 0, 'a')
    | _ -> failwith "Invalid step"

// Walk the maze
let walk (lines: char array array) =
    let rec loop (step: int * int * char) (row, col) =
        let (i, j, c) = step

        // Calculate the new value for this space.
        let footPrint = lines[row][col]
        let footPrintByte = uint8 footPrint
        let newFootPrint =
            if pathMask &&& footPrintByte = pathMask then
                char (footPrintByte ||| (uint8 c))  // Merge with footprint
            else
                c  // Replace space with footprint

        lines[row][col] <- newFootPrint
        let nextRow, nextCol = row + i, col + j
        if footPrint = newFootPrint then
            InfiniteLoop
        elif nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols then
            Escaped
        elif lines[nextRow][nextCol] = '#' then
            // Turn right and continue
            loop (turnRight step) (row, col)
        else
            // Move to the next cell
            loop step (nextRow, nextCol)

    loop (-1, 0, 'a') startPos

// Part 1: Count path footprints
let part1 =
    let lines = input |> Array.map (fun line -> line.ToCharArray())
    walk lines |> ignore

    let isPathChar (c: char) = pathMask = ((uint8 c) &&& pathMask)
    let count =
        lines
        |> Array.sumBy (fun row -> row |> Array.filter isPathChar |> Array.length)

    printfn "part1 %d" count

// Part 2: Check all possible blockages
let part2 =
    let isInfiniteLoop row col =
        let lines = input |> Array.map (fun line -> line.ToCharArray())
        lines[row][col] <- '#'
        walk lines = InfiniteLoop

    let count =
        [ for row in 0 .. rows - 1 do
            for col in 0 .. cols - 1 do
                if isInfiniteLoop row col then 1 else 0 ]
        |> List.sum

    printfn "part2 %d" count
1 Like
3

Hey @surferjeff,

I would suggest making start_pos immutable in the following way:

let start_pos  =
    let mutable start_pos = (-1,-1)
    for ... do
       (...)
    start_pos

Now the mutability of start_pos is confined to the region you really intended to mutate it in.

In general any while loop can be rewritten as a tail recursive function call. My opinion is that tail recursive functions makes it easier to express “early return” type logic. Because it is tail recursive, this has the same performance characteristics as the while loop (in particular, it uses constant stack space)

I have “naively” rewritten your code without changing too much of the logic, simply rewriting the while loop to a recursive function and eliminating the unused WalkResult data type (although you might leave it in for readability, doesn’t seem to hurt), to show what I have in mind:

let walk2 (lines: char array array) =
    let rec update step pos = 
        let (row, col) = pos
        let (i, j, c) = step
        let footPrint = lines[row][col]
        let footPrintByte = uint8 footPrint
        let newFootPrint =
            if pathMask &&& footPrintByte = pathMask then
                char (footPrintByte ||| (uint8 c))  // Merge with footprint
            else
                c  // Replace space with footprint.
        if footPrint = newFootPrint then () else
        lines[row][col] <- newFootPrint
        // Examine the next space.
        let (row, col) = (row + i, col + j)
        if row < 0 || row >= rows || col < 0 || col >= cols then () else
        if lines[row][col] = '#' then
            // Turn right 90 degrees.
            let step = 
                match step with
                | (-1, 0, 'a') -> (0, 1, 'b')
                | (0, 1, 'b') -> (1, 0, 'd')
                | (1, 0, 'd') -> (0, -1, 'h')
                | (0, -1, 'h') -> (-1, 0, 'a')
                | _bad -> failwith "Bad step"
            update step pos
        else
            update step (row, col) // Leave a footprint in the next space.
    update (-1, 0, 'a') startPos

Returning () in a branch of a conditional functions a lot like an early return in a while loop.

Hopefully I didn’t screw up the code above. A more simple example of what I’m trying to convey, less likely to contain bugs, is that these two functions f and g are equivalent.

let f x y z = 
  let mutable result = None
  let mutable statevar1 = initial1_of x y z
  let mutable statevar2 = initial2_of x y z
  while Option.isNone result do
      (statevar1, statevar2) <- business_logic1 statevar1 statevar2 // Updates the state variables
      if test1 statevar1 statevar2 then
         result <- Some (p statevar1 statevar2)
      else
         (statevar1, statevar2) <- business_logic1 statevar1 statevar2 // Updates the state variables
         if test2 statevar1 statevar2 then
            result <- Some (q statevar1 statevar2)
  Option.get result

let g x y z = 
  let rec update statevar1 statevar2 = 
    let (statevar1, statevar2) = business_logic1 statevar1 statevar2
    if test1 statevar1 statevar2 then (p statevar1 statevar2) else
    let (statevar1, statevar2) = business_logic2 statevar1 statevar2 
    if test2 statevar1 statevar2 then (q statevar1 statevar2) else
    update statevar1 statevar2
  update (initial1_of x y z) (initial2_of x y z)