This article is reprinted with my personal public number: Kotlin Maintenance workshop original publication date: 2020-09-09
This article is a reading note. Recently, I have been reading two Haskell books at the same time: “Haskell Fun Guide” and “Magic Haskell”. As a beginner in the field of functional programming, I often need to re-read and re-think in the process of reading, so THAT I can often get some new ideas. The problems described in this article can be solved tightly around two core points in functional programming:
Use the right type design to describe the problem. 2. Almost all functions that recursively process lists can be implemented using folds
In the introduction to Haskell’s Guide to Fun Learning, the author says: “Instead of telling the computer ‘what to do’ as in an imperative language, you describe the problem ‘what is’ by using functions……” So how to describe what the problem is, the design of the type becomes very important. In functional programming, the distinction between a function and a value is not very clear. We can think of both as functions, and then a value is just a function with no arguments and only a return value. We can also think of them all as values, so that a function is simply a more complex value of types combined in a particular form; Another way to look at it is that function types are changed by passing arguments and getting results and this is actually the case with corritization by binding arguments. Thus, in functional programming, the use of the type system abstracts the whole problem even more than in object-oriented programming.
Fold functions (foldl, Foldr, etc.) are a core function in functional programming. They are very important in Haskell and we use them a lot. Functions are also available in the Kotlin library, but because Kotlin is not a purely functional programming language, the use of the fold function is much reduced, and this article will illustrate the magic of the fold function.
Chapter 10 of the Haskell Guide to Fun Learning lists two typical problems that can be solved using functional programming ideas. Calculator is a “reverse polish”, the other is “to London from heathrow airport”, which is relatively more complex, more can reflect the thought of this article wants to convey, so we will be behind the problem step by step, and use the Kotlin implement, to deepen our use of functional programming ideas.
Let’s start by describing our problem, from Heathrow to London:
Suppose we are on a business trip, the plane has arrived in the UK, and we hire a car. There’s a meeting coming up soon and we need to get from Heathrow to London as quickly as possible (as long as it’s safe).
There are two main roads from Heathrow to London, and there are some small roads connecting them. The amount of time it takes to travel between two junctions is fixed. It’s up to us to find the best route to get to London on time for the meeting. We start from the road on the left and can either turn to the other road or go straight ahead.
So let’s directly use the illustration in the original book to have a visual look at the problem description and understand the specific time spent on each section:
The two main roads are A and B, and the final destination is A4 or B4. The path in the middle can be collectively referred to as C. We use A1 and A2…… for the intersection of path and main road B1, B2… To represent. Our aim is to find the fastest route.
Due to space problems, I try to use my own concise language to describe the solution in the original book, because the focus of this article is still Kotlin code, if you want to understand the solution ideas through words, it is recommended to read the original book.
Forget the code and the program, what if we tried to solve this problem manually? We will start from A and B respectively, build two paths, and then add the shortest time from the starting point to the next intersection (which may be A or B) as the new route to the original route, and then calculate backwards in order to compare which of the two routes is shorter. Based on the idea of solving the problem, we abstracted the Section from the starting point of A trunk road to A1, the Section from the starting point of B to B1, and the connecting path between A1 and B1 as A Section, and the following and so on.
We’ll type the Section first:
data class Section(val a: Int, val b: Int, val c: Int)
typealias RoadSystem = List<Section>
Copy the codeWe first define the Section type with data Class. So the RoadSystem is a list of sections. For convenience, we define it as RoadSystem using the type alias.
The road system from Heathrow airport to London can be expressed as:
val heathrowToLondon: RoadSystem = listOf(
Section(a = 50, b = 10, c = 30),
Section(a = 5 , b = 90, c = 20),
Section(a = 40, b = 2 , c = 25),
Section(a = 10, b = 8 , c = 0 )
)
Copy the codeWhat is the type of function that we want to find the best path for? It should accept the road system type as a parameter and return the route. Routes should also be represented as a list, which should contain two pieces of information, 1. Which way is located, 2. How long does it take? Therefore, the route can be expressed as:
enum class Label {
A { override fun toString(): String = "A" },
B { override fun toString(): String = "B" },
C { override fun toString(): String = "C" };
}
typealias Path = List<Pair<Label, Int>>
Copy the codeOf course, we first define an enumeration type Label to represent the path.
Therefore, the function to obtain the optimal route should be defined as:
fun optimalPath(roadSystem: RoadSystem): Path
Copy the codeThink back to the steps we took when we manually solved the problem. We got the Path by iterating through each Section, and then added up the resulting paths. This is where the fold function comes in. We keep collapsing the list of sections (RoadSystem) and reducing it to a list of paths (Path).
When we manually solve, we have been repeating A step, that is, according to the best route to reach the current A road and B road, calculate the best route to reach the next lot A road and B road. So if this step were written as a function, the function type would look like this:
(Pair<Path, Path>, Section) -> Pair<Path, Path>
Copy the codeThis function is actually the function that will be the argument to our fold function, and we’ll implement it now:
fun roadStep(pair: Pair<Path, Path>, section: Section): Pair<Path, Path> { val (pathA, pathB) = pair val (a, b, c) = section val timeA = pathA.map(Pair<Label, Int>::second).sum() val timeB = pathB.map(Pair<Label, Int>::second).sum() val forwardTimeToA = timeA + a val crossTimeToA = timeB + b + c val forwardTimeToB = timeB + b val crossTimeToB = timeA + a + c val newPathToA = mutableListOf<Pair<Label, Int>>().apply { if (forwardTimeToA <= crossTimeToA) { addAll(pathA) add(Label.A to a) } else { addAll(pathB) add(Label.B to b) add(Label.C to c) } } val newPathToB = mutableListOf<Pair<Label, Int>>().apply { if (forwardTimeToB <= crossTimeToB) { addAll(pathB) add(Label.B to b) } else { addAll(pathA) add(Label.A to a) add(Label.C to c) } } return newPathToA to newPathToB }Copy the codeThis may seem like a bit of a typical imperative, but in the Haskell Guide to Fun, the author uses Haskell’s let… in… The expression has a similar effect. Here is a rehash of the code in the book.
In this function we calculate the time it takes to get from A directly to A and from B through C to A, respectively, and the time it takes to get from B directly to B and from A through C to B. Then calculate the length of time separately, and finally return to the new route through comparison.
Finally, we take the fold function as the core of the calculation, determine the two routes recursively, and compare which one is shorter, and finally write the implementation of optimalPath function:
fun optimalPath(roadSystem: RoadSystem): Path =
roadSystem.fold(listOf<Pair<Label, Int>>() to listOf(), ::roadStep).let { (bestAPath, bestBPath) ->
if (bestAPath.map(Pair<Label, Int>::second).sum() <= bestBPath.map(Pair<Label, Int>::second).sum())
bestAPath
else
bestBPath
}
Copy the codeThe final output is printed:
fun main() = println(optimalPath(heathrowToLondon))
Copy the codeThe result is:
[(B, 10), (C, 30), (A, 5), (C, 20), (B, 2), (B, 8), (C, 0)]
Copy the codeSince the last A4 and B4 are at the same place (the time of section C in the middle is 0). So, you end up with an extra (C, 0).
Here is the complete code for the entire problem:
fun main() = println(optimalPath(heathrowToLondon)) data class Section(val a: Int, val b: Int, val c: Int) typealias RoadSystem = List<Section> val heathrowToLondon: RoadSystem = listOf( Section(a = 50, b = 10, c = 30), Section(a = 5 , b = 90, c = 20), Section(a = 40, b = 2 , c = 25), Section(a = 10, b = 8 , c = 0 ) ) enum class Label { A { override fun toString(): String = "A" }, B { override fun toString(): String = "B" }, C { override fun toString(): String = "C" }; } typealias Path = List<Pair<Label, Int>> fun optimalPath(roadSystem: RoadSystem): Path = roadSystem.fold(listOf<Pair<Label, Int>>() to listOf(), ::roadStep).let { (bestAPath, bestBPath) -> if (bestAPath.map(Pair<Label, Int>::second).sum() <= bestBPath.map(Pair<Label, Int>::second).sum()) bestAPath else bestBPath } fun roadStep(pair: Pair<Path, Path>, section: Section): Pair<Path, Path> { val (pathA, pathB) = pair val (a, b, c) = section val timeA = pathA.map(Pair<Label, Int>::second).sum() val timeB = pathB.map(Pair<Label, Int>::second).sum() val forwardTimeToA = timeA + a val crossTimeToA = timeB + b + c val forwardTimeToB = timeB + b val crossTimeToB = timeA + a + c val newPathToA = mutableListOf<Pair<Label, Int>>().apply { if (forwardTimeToA <= crossTimeToA) { addAll(pathA) add(Label.A to a) } else { addAll(pathB) add(Label.B to b) add(Label.C to c) } } val newPathToB = mutableListOf<Pair<Label, Int>>().apply { if (forwardTimeToB <= crossTimeToB) { addAll(pathB) add(Label.B to b) } else { addAll(pathA) add(Label.A to a) add(Label.C to c) } } return newPathToA to newPathToB }Copy the codeOf course, the Haskell code from the original book is given here:
main :: IO ()
main = print . optimalPath $ heathrowToLondon
data Section = Section { getA :: Int, getB :: Int, getC :: Int }
type RoadSystem = [Section]
heathrowToLondon :: RoadSystemheathrowToLondon = [
Section 50 10 30,
Section 5 90 20,
Section 40 2 25,
Section 10 8 0
]
data Label = A | B | C deriving (Show)
type Path = [(Label, Int)]
optimalPath :: RoadSystem -> Path
optimalPath roadSystem =
let (bestAPath, bestBPath) = foldl roadStep ([], []) roadSystem
in if sum (map snd bestAPath) <= sum (map snd bestBPath)
then reverse bestAPath
else reverse bestBPath
roadStep :: (Path, Path) -> Section -> (Path, Path)
roadStep (pathA, pathB) (Section a b c) =
let timeA = sum (map snd pathA)
timeB = sum (map snd pathB)
forwardTimeToA = timeA + a
crossTimeToA = timeB + b + c
forwardTimeToB = timeB + b
crossTimeToB = timeA + a + c
newPathToA = if forwardTimeToA <= crossTimeToA
then (A, a) : pathA
else (C, c) : (B, b) : pathB
newPathToB = if forwardTimeToB <= crossTimeToB
then (B, b) : pathB
else (C, c) : (A, a) : pathA
in (newPathToA, newPathToB)
Copy the codeThere are a few things to note about Kotlin’s version compared to Haskell’s original. 1. Since variables are immutable in Haskell, all changes to a List create a new List. In Kotlin’s implementation, I use a List type instead of a MutableList type for static type declarations. Both return a new list without modifying the previous list. But if you want to write a more space-friendly version, it is recommended to use MutableList. 2. Because of the special nature of lists in Haskell, that is, header inserts are much more efficient than tail inserts, the original Haskell code uses the roadStep function to update Path, and when the optimalPath function returns the result to be displayed, Use the reverse function to reverse the list to get the correct order. In Kotlin, we don’t have this problem. The add function is a tail-insert element, so there is no list inversion in the optimalPath function.
Functional programming is the tool to solve the problem of some, but due to its too “mathematization” also can cause unnecessary overhead of memory, in some time writing the code in the daily work, to make use of functional programming ideas to solve the problem, also want to use modern programming languages are usually more paradigm that advantage to circumvent some will produce negative effect on the “computer science”.