In the most recent post in this series I implemented Tic-Tac-Toe using recursion to find the best moves. The point of that post was the recursion and I took the simplest approach I could think of to represent the actual board and moves. I used two lists of ints, one for each player’s list of occupied squares. The board itself wasn’t explicitly represented at all, it could be inferred from the two lists.
This post looks at a hugely important part of functional programming, Recursion. In simple terms this means writing a function that calls itself. There are endless examples of using recursion to figure out Fibonacci numbers, or process lists. This post will be a little more complicated but hopefully is simple enough that you’ll be able to follow along. We’re going to teach F# to play the perfect game of Tic-Tac-Toe. The game is a favourite for kids, but it quickly becomes boring for adults.
Imagine you have a long running function that you’d like to avoid running unnecessarily. For the purposes of this post you’ll have to suspend disbelief and pretend that negating a number is an expensive task. This example prints out a message so you can see when it actually gets called. let Negate n = printfn "Negating '%A' this is hard work" n -n val Negate : int -> int > Negate 5;; Negating '5' this is hard work val it : int = -5 Now, let’s use that function when writing another.
In my last post I worked through an example that finds the range of numbers that sum to a target value, or gets as close as possible without exceeding the target. I mentioned that the solution felt a little too like the loopy code I would have written in non-functional languages. I felt that there might be a more “functional” way of solving the problem, but I didn’t know what it was.
Another F# session this evening and some more deliberate practice of Functional Thinking. To be fair, this post isn’t really about anything new. If you’ve ever used recursion, even in non-functional languages, this will be old news. If you are new to Functional Programming and/or recursion then this may be useful. Here’s a really simple function. It accepts a number n and sums all the numbers from 1 to n.
Warning, novice functional thinker here. If you know your stuff, what follows may cause distress. I was messing with F# last night and I got a gentle reminder that I’m still a long way from thinking functionally, it still takes a lot of effort. I started with this let evens r = List.filter (fun x -> x % 2 = 0) r > evens [0..10];; val it : int list = [0; 2; 4; 6; 8; 10] Simple enough.