Introduction
In this tutorial, I'll share with you how I built freeCodeCamp's Build a JavaScript Calculator frontend project with Elm.
Here's the live demo of the Elm web application for you to explore how it works. And, here's the reference to its source code.
My primary goal is to share my experience, perspective and processes so that you are exposed to an alternative approach to web application development with Elm. I am not aware of any resources that explain how to develop web applications with Elm that are similar to mine. That's why I thought it might be valuable to share this with the Elm community. I am not trying to teach you Elm, nor am I trying to teach you web application development. All I'm trying to do is to have you take a look over my shoulder as I explain to you how I built the application so that you can be exposed to ideas that could be helpful to you in your own Elm projects.
Audience
Any web developer interested in using Elm to build maintainable, testable, and reliable web applications.
Prerequisites
- A basic knowledge of HTML, CSS, and JavaScript.
- A basic knowledge of web application development. For e.g. if you've had exposure to React, Vue.js, Angular, Ember.js or something else, it would be helpful.
- And, a basic knowledge of Elm as provided by the official Elm guide.
Exposure
As I've stated before, I'm not intentionally trying to teach you anything in particular. That's why there are no learning outcomes. However, I am delibrately trying to expose you to ideas. As many ideas as it takes to develop the application in an honest and realistic way. So, after completing this tutorial I hope you will have been exposed to:
- A process for building any Elm web application starting from a given design.
- A bottom-up approach for building reliable UIs with HTML/CSS that's easy to maintain and extend.
- This approach which I independently discovered and adopted, I recently learned, is similar in spirit to Component Driven Development and Atomic Design.
- A way to prototype with HTML/CSS.
- I also recently learned that what I have is a poor man's version of Storybook. And, the general idea is related to Brad Frost's frontend workshop environment idea.
- A way to structure your HTML/CSS with BEM.
- A way to design an API for your Elm views.
- A way to separate your UI and application logic.
- Unit testing.
Other interesting things you'd be exposed to because I'm working on a calculator, include:
- Building a module for rational number arithmetic.
- Displaying rational numbers using decimal notation for both terminating and repeating decimals.
- Building a module for a Stack data structure.
- Evaluating infix expressions using Dijkstra's shunting yard algorithm.
- Tokenizing user input using a finite-state machine.
The 10,000 Foot View
Design
My process starts with knowing what I want to build and how I want it to look. Design is important but it has a separate process that is outside the scope of this tutorial. The design for the calculator was inspired by lifted from this CodePen example. Thanks Peter Weinberg.
Prototype
The next step in my process is realizing the design using HTML, CSS, and possibly JavaScript. I call this my prototyping phase. Three key concepts support this phase:
- HTML is for structure and semantics (meaning).
- CSS is for styling and layout.
- JavaScript is for controlling dynamic behaviour and managing application logic.
In practice, by keeping these concepts in mind, it helps me to have a clear separation between the user interface (UI) and the application logic. The UI consists of HTML, CSS, and some JavaScript for controlling dynamic behaviour. The application logic consists entriely of JavaScript.
The main goal I try to achieve in this phase is to solve most if not all the UI related problems that the design surfaces. This phase is the phase to figure out HTML semantics, CSS selector names, accessibility, layout, etc.
HTML/CSS to Elm
At this point in the process most if not all of my UI related problems have been solved and it's time to translate the HTML portion into elm/html. This is typically straightforward to do but there is a little bit of view function API design that tends to occur. However, this is definitely the easiest part of the entire process.
Application Logic
The brains of the application is managed by JavaScript and hence, in our case as Elm developers, by Elm. In this part of the process I build a logical model for the application domain. Elm really shines during this part of the process because functional programming using modules, opaque types, union types, pattern matching, immutable data types, and pure functions supports a delightful approach to data modeling.
I don't practice test-driven development but I do test and unit testing the tricky parts of my application logic helps me to find and fix bugs.
Web Application = UI + Application Logic
Finally, I connect the UI with the application logic. The UI provides the means by which input gets passed to the API that models the application domain.
Prototyping
This is the phase where I go from design to prototype.
From Design to Prototype
I take the given design and I reimagine it as an exploded-view drawing that I then use to deconstruct it into its components. I build a dependency graph of all the components such that there is a directed edge from component A to component B whenever A depends on B. A topological sort of this dependency graph helps me figure out in what order to start working on the components. At this point, I have a choice to take either a bottom-up or top-down approach, and I usually choose the bottom-up approach. For each component, I determine:
- How I'm going to give it meaning and structure with HTML.
- How I'm going to refer to its elements using CSS classes.
- How I'm going to present it, as specified in the design, with CSS rules.
Specifics
I use:
- BEM's naming convention for my CSS classes.
- Dart Sass to generate my CSS and I take full advantage of its support for modules via the
@userule.
Blocks
Based on the approach I described in "From Design to Prototype", the components I came up with and their bottom-up ordering are as follows:
- Key -
AC,=,.,+,-,×,÷, and the digits0to9. - Pad - The keypad that houses the keys.
- Display - A two line display. One line to show the user's input and another line to show the result of evaluating that input.
- Calculator - Holds the display and pad.
- Attribution - A note about the developer of the application.
- Page - A container to layout the calculator and attribution.
These components became the blocks of my UI, in accordance with BEM. I worked on each block, one at a time, in bottom-up order until all the blocks were implemented.
key
A key, for e.g. AC, =, ., +, -, ×, ÷, and the digits 0 to 9.
HTML
Default
<button class="key" type="button">8</button>
A key can be clicked and would need a click handler so the <button> element seems appropriate.
By default, a <button> element has its type attribute set to submit. Since the <button> element backing a key won't be for submitting form data to a server it's recommend to set its type attribute to button.
Primary
<button class="key key--primary" type="button">AC</button>
Secondary
<button class="key key--secondary" type="button">=</button>
Since keys only have a style modifier I chose to keep the naming simple. No modifier signals the default and the key--primary and key--secondary block modifiers signal the primary and secondary styles respectively. An alternative naming system for the style modifier could have been:
- The two dashes style with modifier name and value
key--style--default,key--style--primary,key--style--secondary
Sass
@use "../colors";
/*button*/.key {
border: 0;
padding: 0;
display: block;
width: 100%;
height: 100%;
font-size: 1.25rem;
background-color: colors.$matterhorn;
color: colors.$white;
cursor: pointer;
}
.key:hover {
outline: 1px solid colors.$grey;
color: colors.$black;
}
.key--primary {
background-color: colors.$mediumCarmine;
}
.key--secondary {
background-color: colors.$prussianBlue;
}
Colors
I prefer to refer to my colors by name. I like the approach outlined by Sacha Grief in SASS & Color Variables but I didn't follow the two-tier system here since I didn't need it. I only used descriptive names. However, if I decide I want to make the application themeable then adding functional names would be quite useful.
What's with the /*button*/ Comment?
I picked it up from Harry Roberts. In CSS Guidelines, he shares the idea of using quasi-qualified selectors to provide information about where a class might be expected or intended to be used. By using quasi-qualified selectors we can still provide that information without actually qualifying the selector and increasing its specificity.
Key Shape
The key should take up the full width and height of its parent. This allows the parent to control the shape of the key. We need this flexibility because of how the AC and = keys are intended to be displayed.
Demo
Source Code
pad
The pad or keypad consists of the set of keys arranged in a grid.
HTML
<div class="pad">
<div class="pad__slot r0 c0 colspan2">
<button class="key key--primary" type="button">AC</button>
</div>
<div class="pad__slot r0 c2">
<button class="key" type="button">÷</button>
</div>
<div class="pad__slot r0 c3">
<button class="key" type="button">×</button>
</div>
<div class="pad__slot r1 c0">
<button class="key" type="button">7</button>
</div>
<div class="pad__slot r1 c1">
<button class="key" type="button">8</button>
</div>
<div class="pad__slot r1 c2">
<button class="key" type="button">9</button>
</div>
<div class="pad__slot r1 c3">
<button class="key" type="button">-</button>
</div>
<div class="pad__slot r2 c0">
<button class="key" type="button">4</button>
</div>
<div class="pad__slot r2 c1">
<button class="key" type="button">5</button>
</div>
<div class="pad__slot r2 c2">
<button class="key" type="button">6</button>
</div>
<div class="pad__slot r2 c3">
<button class="key" type="button">+</button>
</div>
<div class="pad__slot r3 c0">
<button class="key" type="button">1</button>
</div>
<div class="pad__slot r3 c1">
<button class="key" type="button">2</button>
</div>
<div class="pad__slot r3 c2">
<button class="key" type="button">3</button>
</div>
<div class="pad__slot r3 c3 rowspan2">
<button class="key key--secondary" type="button">=</button>
</div>
<div class="pad__slot r4 c0 colspan2">
<button class="key" type="button">0</button>
</div>
<div class="pad__slot r4 c2">
<button class="key" type="button">.</button>
</div>
</div>
The pad contains slots for the keys. I made the deliberate choice to style the position and size of each slot using utility classes scoped to the slots.
Sass
@use "../colors";
$pad-slot-width: 80px !default;
$pad-slot-height: 65px !default;
$pad-slot-spacing-around: 1px !default;
$pad-width: 4 * $pad-slot-width + 5 * $pad-slot-spacing-around;
$pad-height: 5 * $pad-slot-height + 6 * $pad-slot-spacing-around;
.pad {
position: relative;
width: $pad-width;
height: $pad-height;
background-color: colors.$black;
}
.pad__slot {
position: absolute;
width: $pad-slot-width;
height: $pad-slot-height;
}
.pad__slot.r0 {
top: $pad-slot-spacing-around;
}
.pad__slot.r1 {
top: $pad-slot-height + 2 * $pad-slot-spacing-around;
}
.pad__slot.r2 {
top: 2 * $pad-slot-height + 3 * $pad-slot-spacing-around;
}
.pad__slot.r3 {
top: 3 * $pad-slot-height + 4 * $pad-slot-spacing-around;
}
.pad__slot.r4 {
top: 4 * $pad-slot-height + 5 * $pad-slot-spacing-around;
}
.pad__slot.c0 {
left: $pad-slot-spacing-around;
}
.pad__slot.c1 {
left: $pad-slot-width + 2 * $pad-slot-spacing-around;
}
.pad__slot.c2 {
left: 2 * $pad-slot-width + 3 * $pad-slot-spacing-around;
}
.pad__slot.c3 {
left: 3 * $pad-slot-width + 4 * $pad-slot-spacing-around;
}
.pad__slot.rowspan2 {
height: 2 * $pad-slot-height + $pad-slot-spacing-around;
}
.pad__slot.colspan2 {
width: 2 * $pad-slot-width + $pad-slot-spacing-around;
}
The width, height, and spacing around the slots can each be overriden when using the pad module. For e.g.
@use "blocks/pad" with (
$pad-slot-width: 75px,
$pad-slot-height: 50px,
$pad-slot-spacing-around: 2px
);
Demo
Source Code
display
A two line display where the top line shows the user's input and the bottom line shows the result of evaluating that input.
HTML
Empty
<div class="display">
<div class="display__line1"></div>
<div class="display__line2"></div>
</div>
It's interesting that even though the structure is simple and it seems like nothing could be improved, there is room for improvement. In particular, I recently learned about the <output> element. It is a container element into which you can inject the results of a calculation or the outcome of a user action. Thus, both display lines could be changed from <div> to <output> to improve their semantics and accessibility.
Non-empty: Short
<div class="display">
<div class="display__line1">22÷7=3.(142857)</div>
<div class="display__line2">3.(142857)</div>
</div>
Non-empty: Long
<div class="display">
<div class="display__line1">1×8111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111</div>
<div class="display__line2">8111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111</div>
</div>
While I was playing around with the display I realized that long input text broke it and it forced me to handle that case immediately. This is one of the major benefits of working through UI problems, in a dedicated environment, independently of everything else.
Sass
@use "../colors";
@use "../typography";
.display {
padding: 5px 5px 10px 5px;
font-family: typography.$digital;
text-align: right;
overflow-wrap: break-word;
background-color: colors.$black;
}
.display__line1:empty::before,
.display__line2:empty::before {
content: "\00A0";
}
.display__line1 {
padding-bottom: 2px;
font-size: 1.25rem;
line-height: 1;
color: colors.$orange;
}
.display__line2 {
font-size: 1.875rem;
line-height: 1;
color: colors.$white;
}
Typography
I prefer to refer to my font stacks by name, just as I do with colors. A two-tier system can be established here as well.
The Empty State
When the display lines are empty they collapse on themselves. In order to avoid that from happening I use the :empty CSS pseudo-class to select the lines when they have no children and add content, a non-breaking space, to them. This ensures that they don't collapse and the height of the lines remain intact.
Long Text
The following two CSS rules ensure that long text, within the lines, is handled correctly.
.display {
overflow-wrap: break-word;
}
.display__line1, .display__line2 {
line-height: 1;
}
Writing Sass
Sometimes I write my Sass based on the problems a group of rules are intended to solve. For e.g. I might rewrite the Sass above in the following way:
@use "../colors";
@use "../typography";
// Block
.display {
padding: 5px 5px 10px 5px;
font-family: typography.$digital;
text-align: right;
background-color: colors.$black;
}
// Elements
.display__line1 {
padding-bottom: 2px;
font-size: 1.25rem;
color: colors.$orange;
}
.display__line2 {
font-size: 1.875rem;
color: colors.$white;
}
// Deal with the empty state
.display__line1:empty::before,
.display__line2:empty::before {
content: "\00A0";
}
// Deal with long text
.display {
overflow-wrap: break-word;
}
.display__line1, .display__line2 {
line-height: 1;
}
Demo
Source Code
calculator
The calculator consists of the display and pad arranged in a column.
HTML
<div class="calculator">
<div class="calculator__display">
<!-- The display goes here. -->
</div>
<div class="calculator__pad">
<!-- The pad goes here. -->
</div>
</div>
Sass
@use "../colors";
@use "./pad";
.calculator {
display: inline-flex;
flex-direction: column;
border: 2px solid colors.$cornFlowerBlue;
padding: 3px;
background-color: colors.$black;
}
.calculator__display {
width: pad.$pad-width;
}
Who Controls the Width?
The width of the display is constrained to be equal to the width of the pad, pad.$pad-width, by setting the width of the .calculator__display element and not by setting the width of the .display block directly. This is because the .display block is designed to take on the width of its container. As such, it is up to the container to set the width.
The .calculator__pad Element
I don't explicitly style the .calculator__pad element. However, it does serve two purposes:
- The
.calculatorblock usesdisplay: inline-flexwhich means the.calculator__padelement becomes a flex item. This is a good thing because it protects the.padblock from becoming a flex item itself which could mess with its dimensions. - Naming the wrapping
div, i.e..calculator__pad, allows me to refer to it by name. So it's good for communication.
Demo
Source Code
attribution
The attribution contains information about the developer of the web application.
HTML
<p class="attribution">Developed by <a class="attribution__link" href="https://github.com/dwayne" target="_blank" title="Dwayne's GitHub profile">Dwayne Crooks</a></p>
Sass
@use "../colors";
@use "../typography";
/*p*/.attribution {
margin: 0;
font-family: typography.$shareTechMono;
text-align: center;
}
/*a*/.attribution__link {
text-decoration: none;
color: colors.$prussianBlue;
}
Demo
Source Code
page
The page composes all the components to form the user interface for the entire web application.
HTML
<div class="page">
<div class="page__wrapper">
<div class="page__content">
<main>
<!-- The calculator goes here. -->
</main>
<footer>
<!-- The attribution goes here. -->
</footer>
</div>
</div>
</div>
The <main> element represents the dominant content of the <body> of a document. That's why I made the calculator a child of that element.
Sass
@use "../layouts";
.page {
@include layouts.absolute-center(20px);
}
.page__content {
@include layouts.centered-column(15px);
}
Mixins
The .page block and .page__content element both make use of general layout patterns that I made reusable with mixins.
@mixin centered-column($gap) {
display: flex;
flex-direction: column;
align-items: center;
gap: $gap;
}
@mixin absolute-center($padding, $height: 100vh) {
display: flex;
height: $height;
&__wrapper {
padding: $padding;
//
// Ensures the padding is shown when the content overflows its container.
//
display: inline-block;
//
// Vertically and horizontally center.
//
margin: auto;
}
}
Here's the CSS that's generated:
.page {
display: flex;
height: 100vh;
}
.page__wrapper {
padding: 20px;
display: inline-block;
margin: auto;
}
.page__content {
display: flex;
flex-direction: column;
align-items: center;
gap: 15px;
}
Demo
Source Code
Translating
This is the phase where I go from prototype to Elm views.
From Prototype to Elm Views
At this point in the process I am usually highly confident in the reliability of my user interface. I built and manually tested the user interface independent of any JavaScript framework, independent of any application logic, and closely following web development best practices and standards as far as I understand it.
I now begin introducing Elm into the process and I continue to keep my focus on the user interface.
The goal of this part of the process is to use elm/html to abstract over the HTML/CSS that I created during the prototyping phase so that I can compose the components, i.e. view functions, in any way I chose.
The general approach that has been working for me is to map each block to a module that implements the view for that component. For e.g. the .key block would be mapped to the View.Key module which exports a view function. The view function abstracts over the HTML of the .key block. Any modifiers on the blocks and elements become options to the view function that help decide which HTML elements and attributes are used.
My view functions typically take one of three forms:
view : Html msgview : ViewOptions -> Html msgview : ViewOptions msg -> Html msg
Views
The blocks map to modules as follows:
| Block | Module |
|---|---|
| key | View.Key |
| pad | View.Pad |
| display | View.Display |
| calculator | View.Calculator |
| attribution | View.Attribution |
| page | View.Page |
View.Key
The implementation was based on the .key block.
View Options
type alias ViewOptions msg =
{ style : Style
, key : Key
, onClick : Key -> msg
}
type Style
= Default
| Primary
| Secondary
The Style Block Modifiers
The Style custom type is used to determine when to apply the .key--primary and .key--secondary block modifiers.
The Logical Representation of a Key
This module provides a visual representation of a key but I also needed a logical representation which I implemented in Data.Key, Data.Digit, and Data.Operator.
Data.Key
type Key
= AC
| Dot
| Equal
| Digit Digit
| Operator Operator
toString : Key -> String
toString key =
case key of
AC ->
"AC"
Dot ->
"."
Equal ->
"="
Digit digit ->
Digit.toString digit
Operator operator ->
Operator.toString operator
Data.Digit
type Digit
= Zero
| One
| Two
| Three
| Four
| Five
| Six
| Seven
| Eight
| Nine
toInt : Digit -> Int
toInt digit =
case digit of
Zero ->
0
One ->
1
Two ->
2
Three ->
3
Four ->
4
Five ->
5
Six ->
6
Seven ->
7
Eight ->
8
Nine ->
9
toString : Digit -> String
toString digit =
case digit of
Zero ->
"0"
One ->
"1"
Two ->
"2"
Three ->
"3"
Four ->
"4"
Five ->
"5"
Six ->
"6"
Seven ->
"7"
Eight ->
"8"
Nine ->
"9"
Data.Operator
type Operator
= Add
| Sub
| Mul
| Div
toString : Operator -> String
toString operator =
case operator of
Add ->
"+"
Sub ->
"-"
Mul ->
"×"
Div ->
"÷"
View Function
view : ViewOptions msg -> H.Html msg
view { style, key, onClick } =
H.button
[ HA.class "key"
, HA.class <|
case style of
Default ->
""
Primary ->
"key--primary"
Secondary ->
"key--secondary"
, HA.type_ "button"
, HE.onClick <| onClick key
]
[ H.text <| Key.toString key ]
Source Code
View.Pad
The implementation was based on the .pad block.
View Options
view : (Key -> msg) -> H.Html msg
view onClick =
-- ...
Since I only needed one option, i.e. onClick, I didn't create a ViewOptions type alias.
View Function
view : (Key -> msg) -> H.Html msg
view onClick =
H.div [ HA.class "pad" ]
[ viewPadSlot
{ position = ( 0, 0 )
, span = Just Colspan
, style = Key.Primary
, key = Key.AC
, onClick = onClick
}
, viewPadSlot
{ position = ( 0, 2 )
, span = Nothing
, style = Key.Default
, key = Key.Operator Operator.Div
, onClick = onClick
}
, viewPadSlot
{ position = ( 0, 3 )
, span = Nothing
, style = Key.Default
, key = Key.Operator Operator.Mul
, onClick = onClick
}
, viewPadSlot
{ position = ( 1, 0 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Seven
, onClick = onClick
}
, viewPadSlot
{ position = ( 1, 1 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Eight
, onClick = onClick
}
, viewPadSlot
{ position = ( 1, 2 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Nine
, onClick = onClick
}
, viewPadSlot
{ position = ( 1, 3 )
, span = Nothing
, style = Key.Default
, key = Key.Operator Operator.Sub
, onClick = onClick
}
, viewPadSlot
{ position = ( 2, 0 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Four
, onClick = onClick
}
, viewPadSlot
{ position = ( 2, 1 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Five
, onClick = onClick
}
, viewPadSlot
{ position = ( 2, 2 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Six
, onClick = onClick
}
, viewPadSlot
{ position = ( 2, 3 )
, span = Nothing
, style = Key.Default
, key = Key.Operator Operator.Add
, onClick = onClick
}
, viewPadSlot
{ position = ( 3, 0 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.One
, onClick = onClick
}
, viewPadSlot
{ position = ( 3, 1 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Two
, onClick = onClick
}
, viewPadSlot
{ position = ( 3, 2 )
, span = Nothing
, style = Key.Default
, key = Key.Digit Digit.Three
, onClick = onClick
}
, viewPadSlot
{ position = ( 3, 3 )
, span = Just Rowspan
, style = Key.Secondary
, key = Key.Equal
, onClick = onClick
}
, viewPadSlot
{ position = ( 4, 0 )
, span = Just Colspan
, style = Key.Default
, key = Key.Digit Digit.Zero
, onClick = onClick
}
, viewPadSlot
{ position = ( 4, 2 )
, span = Nothing
, style = Key.Default
, key = Key.Dot
, onClick = onClick
}
]
viewPadSlot
The viewPadSlot function abstracts over the .pad__slot element. The .pad__slot element itself can be given a row and column position via row and column classes, i.e. .r0, .r1, .r2, .r3, .r4, .c0, .c1, .c2, and .c3, and an optional spanning direction class, i.e. .rowspan2 and .colspan2. It is also the parent of the .key block so I decided to pass along the corresponding View.Key.ViewOptions, i.e. style, key, and onClick.
type Span
= Colspan
| Rowspan
viewPadSlot :
{ position : ( Int, Int )
, span : Maybe Span
, style : Key.Style
, key : Key
, onClick : Key -> msg
}
-> H.Html msg
viewPadSlot { position, span, style, key, onClick } =
let
( r, c ) =
position
in
H.div
[ HA.class "pad__slot"
, HA.class <| "r" ++ String.fromInt r
, HA.class <| "c" ++ String.fromInt c
, HA.class <|
case span of
Nothing ->
""
Just Colspan ->
"colspan2"
Just Rowspan ->
"rowspan2"
]
[ Key.view
{ style = style
, key = key
, onClick = onClick
}
]
An Alternative API
An alternative API for the viewPadSlot function could have been:
viewPadSlot :
{ position : ( Int, Int )
, span : Maybe Span
, key : Key.ViewOptions msg
}
-> H.Html msg
viewPadSlot { position, span, key } =
-- ...
This would have simplified the call to Key.view, it's just Key.view key now, but would have made the viewPadSlot calls more verbose:
viewPadSlot
{ position = ( 0, 0 )
, span = Just Colspan
, key =
{ style = Key.Primary
, key = Key.AC
, onClick = onClick
}
}
Since viewPadSlot is called more than Key.view I decided against this alternative API.
Source Code
View.Display
The implementation was based on the .display block.
View Options
type alias ViewOptions =
{ line1 : String
, line2 : String
}
View Function
view : ViewOptions -> H.Html msg
view { line1, line2 } =
H.div [ HA.class "display" ]
[ H.div [ HA.class "display__line1" ] [ H.text line1 ]
, H.div [ HA.class "display__line2" ] [ H.text line2 ]
]
Source Code
View.Calculator
The implementation was based on the .calculator block.
View Options
type alias ViewOptions msg =
{ line1 : String
, line2 : String
, onClick : Key -> msg
}
View Function
view : ViewOptions msg -> H.Html msg
view { line1, line2, onClick } =
H.div [ HA.class "calculator" ]
[ H.div
[ HA.class "calculator__display" ]
[ Display.view
{ line1 = line1
, line2 = line2
}
]
, H.div
[ HA.class "calculator__pad" ]
[ Pad.view onClick ]
]
Source Code
View.Attribution
The implementation was based on the .attribution block.
View Options
type alias ViewOptions =
{ name : String
, title : String
, url : String
}
View Function
view : ViewOptions -> H.Html msg
view { name, title, url } =
H.p [ HA.class "attribution" ]
[ H.text "Developed by "
, H.a
[ HA.class "attribution__link"
, HA.href url
, HA.target "_blank"
, HA.title title
]
[ H.text name ]
]
Source Code
View.Page
The implementation was based on the .page block.
View Options
type alias ViewOptions msg =
{ calculator : Calculator.ViewOptions msg
, attribution : Attribution.ViewOptions
}
View Function
view : ViewOptions msg -> H.Html msg
view { calculator, attribution } =
H.div [ HA.class "page" ]
[ H.div [ HA.class "page__wrapper" ]
[ H.div [ HA.class "page__content" ]
[ H.main_ [] [ Calculator.view calculator ]
, H.footer [] [ Attribution.view attribution ]
]
]
]
Source Code
Reflections on the UI
The prototyping and translating phases of my process led me to an Elm view, i.e. View.Page.view, that abstracted the user interface of the entire web application. View.Page.view is composed of reusable view functions that I designed based on the blocks, i.e. components, that arose from my decomposition of the design.
View.Page.view
{ calculator =
{ line1 = line1
, line2 = line2
, onClick = onClick
}
, attribution =
{ name = "Dwayne Crooks"
, title = "Dwayne's GitHub profile"
, url = "https://github.com/dwayne"
}
}
All I need in order to display the web application are the two display lines and a click handler. No application logic required. 🙌
Domain Modeling
This is the phase where I build a logical model of the application domain and expose an API that can be used by the UI I built in the previous phases.
Consider a physical digital calculator. It has a casing and some electronics on a circuit board. I think of the UI as the casing and the application logic as the electronics.
I have no prescriptive way of building the logical model. This is a creative process that I approach in incremental steps that allow me to slowly eat away at the problem until I have a solution. Usually the first solution I come up with isn't well refined and it takes me a few more sessions to refactor it into a final form that pleases me.
Preliminary Analysis
Here are some rough notes I used to think about the problem.
- The UI is complete but it's inert
ACmeans "All Clear"- The operations are addition (
+), subtraction (-), multiplication (×), and division (÷) - A user can only enter decimal numbers using the digits
0through9and the decimal point (.) - The non-terminating non-repeating decimal numbers are the irrational numbers
- Can the user enter irrational numbers?
- No, it's not possible with the inputs available
- Can the user enter an expression that evaluates to an irrational number?
- No, it's not possible with the operations available
- It follows that we'd only need support for rational numbers
=means to calculate what's been input- The input appears on line 1 of the display
1 + 2 * 3is a possible infix expression that the user can input- Either
1 + 2 * 3 = 1 + 6 = 7or1 + 2 * 3 = 3 * 3 = 9 - We want the answer to be
7which means we want to respect the usual operator precedence when evaluating expressions - Dijkstra's shunting yard algorithm can be used to help us evaluate the infix expressions while respecting operator precedence
- I was aware of this algorithm from my Computer Science classes
- Alternatively, you could have researched the following question "How does a calculator evaluate infix expressions?", and you would have found answers pointing you in a similar direction. For e.g. when I asked Google I found this Expression Evaluation article
- Either
1 / 3results in the repeating decimal0.333...- We can display repeating decimals by highlighting the repeating digits
- So for e.g. we can display
1 / 3as0.(3)
- From
View.Key, I already identified a need forData.Key,Data.Digit, andData.Operator - The user interacts with the UI by pressing keys on the keypad. These key presses are used to build up an infix expression. When the user is ready to evaluate the infix expression they press the
=key
API Sketch
Based on the preliminary analysis I then thought through what the API could be over several sessions. At this point I was trying to figure out, at a high-level, how all the pieces would fit together to become a cohesive solution to the problem. Some questions I tried to answer included:
- What's the overall shape of the solution?
- What modules do I need?
- What data structures do I need?
- What are the interesting parts that will need more thought?
Data.Calculator
module Data.Calculator exposing
( Calculator
, new
, press
, Output, toOutput
)
import Data.Key exposing (Key)
type Calculator
new : Calculator
press : Key -> Calculator -> Calculator
type alias Output =
{ line1 : String
, line2 : String
}
toOutput : Calculator -> Output
The idea I had in mind is that Data.Calculator would serve as the logical representation of the calculator. It has an internal data structure that it uses to keep track of the infix expression that the users builds one key press at a time.
new creates a calculator in its initial state.
press takes a key pressed by the user and updates the calculator's internal data structures.
toOutput transforms the internal data structures into a format that can be used to display the infix expression that's being built (i.e. line 1) and the user's current input (i.e. line 2).
The key thing would be figuring out what this internal data structure needs to be for the API to work.
Data.Evaluator
module Data.Evaluator exposing (Answer, Error(..), eval)
import Data.Token exposing (Token)
import Lib.Rational exposing (Rational)
type alias Answer =
Result Error Rational
type Error
eval : List Token -> Answer
Recall that I would need to be able to evaluate infix expressions and respect operator precedence. Dijkstra's shunting yard algorithm allows me to do that and Data.Evaluator exports the function eval that implements said algorithm.
Error would enumerate all the possible errors that could occur based on eval's evaluation of the list of tokens.
I'm expecting an infix expression like 1 + 2 * 3 to be represented as a list of tokens as follows:
[ Number (Rational.fromInt 1), Operator Add, Number (Rational.fromInt 2), Operator Mul, Number (Rational.fromInt 3) ]
Hence, part of Data.Calculator's job would be to tokenize the user's input.
Data.Token
module Data.Token exposing (Token(..), toString)
import Data.Operator as Operator exposing (Operator)
import Lib.Rational as Rational exposing (Rational)
type Token
= Number Rational
| Operator Operator
toString : Token -> String
toString token =
case token of
Number r ->
Rational.toDecimalString r
Operator op ->
Operator.toString op
I came up with this based on the tokens I expected to be present in the infix expressions that could be entered by a user.
Lib.Rational
module Lib.Rational exposing
( Rational
, zero, fromInt, new
, add, sub, mul, div
, toString, toDecimalString
)
type Rational
zero : Rational
fromInt : Int -> Rational
new : Int -> Int -> Maybe Rational
add : Rational -> Rational -> Rational
sub : Rational -> Rational -> Rational
mul : Rational -> Rational -> Rational
div : Rational -> Rational -> Rational
toString : Rational -> String
toDecimalString : Rational -> String
zero, fromInt, and new can be used to construct rational numbers.
add, sub, mul, and div perform the usual arithmetic over the rationals. To keep things simple, I define div r zero == zero for every rational number r.
toString converts a rational number to either an integral or fractional string. Here are some examples:
Maybe.map toString (new 0 1) == Just "0"
Maybe.map toString (new 0 2) == Just "0"
Maybe.map toString (new 5 1) == Just "5"
Maybe.map toString (new -5 1) == Just "-5"
Maybe.map toString (new 5 2) == Just "5/2"
Maybe.map toString (new -5 2) == Just "-5/2"
Maybe.map toString (new 5 -2) == Just "-5/2"
Maybe.map toString (new -5 -2) == Just "5/2"
Maybe.map toString (new 3 6) == Just "1/2"
Maybe.map toString (new 6 3) == Just "2"
toDecimalString converts a rational number to a, wait for it, decimal string. Here are some examples:
Maybe.map toDecimalString (new 0 1) == Just "0"
Maybe.map toDecimalString (new 5 1) == Just "5"
Maybe.map toDecimalString (new -5 1) == Just "-5"
Maybe.map toDecimalString (new 0 2) == Just "0"
Maybe.map toDecimalString (new 5 2) == Just "2.5"
Maybe.map toDecimalString (new -5 2) == Just "-2.5"
Maybe.map toDecimalString (new 5 -2) == Just "-2.5"
Maybe.map toDecimalString (new -5 -2) == Just "2.5"
Maybe.map toDecimalString (new 3 6) == Just "0.5"
Maybe.map toDecimalString (new 6 3) == Just "2"
Maybe.map toDecimalString (new 1 3) == Just "0.(3)"
Maybe.map toDecimalString (new 7 12) == Just "0.58(3)"
Maybe.map toDecimalString (new 1 23) == Just "0.(0434782608695652173913)"
The toString and toDecimalString functions are good candidates for unit testing.
Lib.Stack
module Lib.Stack exposing
( Stack
, new
, isEmpty
, push, pop
)
type Stack a
new : Stack a
isEmpty : Stack a -> Bool
push : a -> Stack a -> Stack a
pop : Stack a -> Maybe ( a, Stack a )
Stacks are used in Dijkstra's shunting yard algorithm. There are a few simple ways to implement them so I knew this wasn't going to be a problem.
Questions Answered
After sketching out the API I had a better sense of the shape of the solution, I understood the modules and data structures I needed, and I knew where the tricky bits lay.
Shape of the Solution
-- MODEL
type alias Model =
{ calculator : Calculator
}
init : Model
init =
{ calculator = Calculator.new
}
-- UPDATE
type Msg
= Clicked Key
update : Msg -> Model -> Model
update msg model =
case msg of
Clicked key ->
{ model | calculator = Calculator.press key model.calculator }
-- VIEW
view : Model -> H.Html Msg
view { calculator } =
let
{ line1, line2 } =
Calculator.toOutput calculator
in
Page.view
{ calculator =
{ line1 = line1
, line2 = line2
, onClick = Clicked
}
, attribution =
{ name = "Dwayne Crooks"
, title = "Dwayne's GitHub profile"
, url = "https://github.com/dwayne"
}
}
Modules and Data Structures
Data.CalculatorData.EvaluatorData.TokenLib.RationalLib.Stack
Why Lib?
It's a personal preference of mine to place modules in Lib that I feel are general enough to one day deserve their own library or at least be reused in other projects. By placing them in Lib it's easier for me to identify these reusable modules when I'm scanning through my projects.
The Tricky Bits
These are the parts that are non-trivial to figure out and where I expected to spend most of my time in this phase of the project.
- Group 1
- What's
type Calculatorgoing to be? - How to tokenize the user's input as they press keys?
- How to implement
Calculator.press? - How to implement
Calculator.toOutput?
- What's
- Group 2
- How to implement Dijkstra's shunting yard algorithm,
Evaluator.eval, in a pure functional language?
- How to implement Dijkstra's shunting yard algorithm,
- Group 3
- How to implement
Rational.toDecimalString?
- How to implement
The 3 groups can be worked on independently of each other.
Calculator.press, Calculator.toOutput, Evaluator.eval, and Rational.toDecimalString are great candidates for unit testing. I didn't practice test-driven development but I did cycle between tests and implementation in order to implement the functions.
The Plan
Moving forward we'd tackle and solve the problems of each group in the order: Group 3, Group 2, and Group 1.
Let's get started on the rational numbers.
An Aside: My Historically Accurate First Attempt
This is how I literally first worked my way through the project when I was learning Elm:
- I made the calculator work for
AC,0-9,+/-, and= - I added support for multiplication
- I implemented Dijkstra's shunting yard algorithm to handle operator precedence
- I added support for integer division
- I added support for rational arithmetic
Then, over the years, as my understanding for Elm grew I refactored my first solution into what it is today.
Rational Numbers
A rational number is a real number that can be expressed as the fraction \( \frac{p}{q} \) of two integers with a numerator \( p \) and a non-zero denominator \( q \).
Public API
module Lib.Rational exposing
( Rational
, new, zero, fromInt
, add, sub, mul, div
, toString, toDecimalString
)
-- Representation
type Rational
-- Constructors
new : Int -> Int -> Maybe Rational
zero : Rational
fromInt : Int -> Rational
-- Arithmetic
add : Rational -> Rational -> Rational
sub : Rational -> Rational -> Rational
mul : Rational -> Rational -> Rational
div : Rational -> Rational -> Rational
-- Conversion
toString : Rational -> String
toDecimalString : Rational -> String
Representation
A rational number can be represented as follows:
type Rational
= Rational Int Int
So, for example, one-half can be represented by Rational 1 2.
Zero in the Denominator
By definition, a rational number is not supposed to have a zero in its denominator. But, the above representation doesn't prevent this possibility since, for example, Rational 3 0 is a valid value of type Rational. However, we can control the way values of type Rational get created by not exporting the type's constructor and instead exporting a custom function, in this case new, that constructs values which obey the definition of a rational number.
We call the Rational type an opaque type since its constructors are private to the module. It's opaque because users of the module can't see and thus access the internal details of the type.
We call new a smart constructor because it uses a bit of logic to decide how and when to construct a value of type Rational.
Equivalent Rational Numbers
One-half can also be represented by Rational 2 4, Rational 3 6, Rational 4 8, and so on. I decided to use the representation that had all common factors removed from both the numerator and denominator.
Negative Rational Numbers
Negative one-half can be represented by Rational -1 2 or Rational 1 -2. I decided to represent negative rational numbers such that the numerator always contains the negative value.
Constructors
new
Based on the decisions I made in Representation I came up with the following requirements for new.
new 1 2 == Just (Rational 1 2)
new 3 0 == Nothing
new 2 4 == Just (Rational 1 2)
new 3 6 == Just (Rational 1 2)
new 4 8 == Just (Rational 1 2)
new -1 2 == Just (Rational -1 2)
new 1 -2 == Just (Rational -1 2)
new -1 -2 == Just (Rational 1 2)
new -2 4 == Just (Rational -1 2)
new 2 -4 == Just (Rational -1 2)
new -2 -4 == Just (Rational 1 2)
The following implementation satisfies the requirements:
new : Int -> Int -> Maybe Rational
new numer denom =
if denom == 0 then
Nothing
else
Just (makeRational numer denom)
makeRational : Int -> Int -> Rational
makeRational numer denom =
let
divisor =
gcd numer denom
g =
if denom < 0 then
-divisor
else
divisor
n =
numer // g
d =
denom // g
in
Rational n d
gcd : Int -> Int -> Int
gcd a b =
gcdHelper (abs a) (abs b)
gcdHelper : Int -> Int -> Int
gcdHelper a b =
if b == 0 then
a
else
gcdHelper b (modBy b a)
To remove all the common factors from both the numerator and denominator I divide both by their greatest common divisor. gcd implements the Euclidean algorithm, which is an efficient method for computing the greatest common divisor (GCD) of two integers.
gcdHelper is implemented using tail-recursion so that it can be optimized into a loop.
I tested that new met the requirements using elm repl. The unit tests came later.
Convenient Constructors
Having to deal with Maybe everytime you need a rational number can become tedious. The zero and fromInt constructors make it quite easy to create the rational numbers for zero and the other integers.
zero
zero : Rational
zero =
Rational 0 1
fromInt
fromInt : Rational
fromInt n =
Rational n 1
Arithmetic
Addition
\[ \frac{n_1}{d_1} + \frac{n_2}{d_2} = \frac{n_1d_2 + n_2d_1}{d_1d_2} \]
add : Rational -> Rational -> Rational
add (Rational n1 d1) (Rational n2 d2) =
makeRational (n1 * d2 + n2 * d1) (d1 * d2)
Subtraction
\[ \frac{n_1}{d_1} - \frac{n_2}{d_2} = \frac{n_1d_2 - n_2d_1}{d_1d_2} \]
sub : Rational -> Rational -> Rational
sub (Rational n1 d1) (Rational n2 d2) =
makeRational (n1 * d2 - n2 * d1) (d1 * d2)
Multiplication
\[ \frac{n_1}{d_1} \times \frac{n_2}{d_2} = \frac{n_1n_2}{d_1d_2} \]
mul : Rational -> Rational -> Rational
mul (Rational n1 d1) (Rational n2 d2) =
makeRational (n1 * n2) (d1 * d2)
Division
\[ \frac{n_1}{d_1} \div \frac{n_2}{d_2} = \frac{n_1}{d_1} \times \frac{d_2}{n_2} = \frac{n_1d_2}{d_1n_2} \text{, } n_2 \neq 0 \]
div : Rational -> Rational -> Rational
div (Rational n1 d1) (Rational n2 d2) =
if n2 == 0 then
zero
else
makeRational (n1 * d2) (d1 * n2)
For division by zero, I chose to return the zero rational number rather than to signal an error.
Exercise
Implement div : Rational -> Rational -> Maybe Rational, such that div r zero == Nothing, and solve the downstream consequences of this change.
Conversion
toString
It converts a rational number to either an integral or fractional string. The requirements are:
toString zero == "0"
-- A good candidate for a fuzz test:
toString (fromInt n) == String.fromInt n
Maybe.map toString (new 5 2) == Just "5/2"
Maybe.map toString (new -5 2) == Just "-5/2"
Maybe.map toString (new 5 -2) == Just "-5/2"
Maybe.map toString (new -5 -2) == Just "5/2"
Maybe.map toString (new 3 6) == Just "1/2"
Maybe.map toString (new 6 3) == Just "2"
The following implementation satisfies the requirements:
toString : Rational -> String
toString (Rational n d) =
if d == 1 then
String.fromInt n
else
String.fromInt n ++ "/" ++ String.fromInt d
n and d have no common factors because of the ways in which rational numbers can constructed. So we know the rational number is in lowest terms. Also, if the rational number is negative then n is negative and d is positive so we don't need to worry about where to place the minus sign. If d is 1 then we return the string representation of the integer n. Otherwise, we return the string representation of the integer n over the string representation of the integer d.
toDecimalString
It converts a rational number to either an integral or decimal string. The requirements are:
toDecimalString zero == "0"
-- Another good candidate for a fuzz test:
toDecimalString (fromInt n) == String.fromInt n
Maybe.map toDecimalString (new 5 2) == Just "2.5"
Maybe.map toDecimalString (new -5 2) == Just "-2.5"
Maybe.map toDecimalString (new 5 -2) == Just "-2.5"
Maybe.map toDecimalString (new -5 -2) == Just "2.5"
Maybe.map toDecimalString (new 3 6) == Just "0.5"
Maybe.map toDecimalString (new 6 3) == Just "2"
Maybe.map toDecimalString (new 1 3) == Just "0.(3)"
Maybe.map toDecimalString (new 7 12) == Just "0.58(3)"
Maybe.map toDecimalString (new 1 23) == Just "0.(0434782608695652173913)"
Here's the start of an implementation that satisfies the requirements:
toDecimalString : Rational -> String
toDecimalString (Rational n d) =
if d == 1 then
String.fromInt n
else
let
sign =
if n < 0 then
"-"
else
""
m =
abs n
quotient =
m // d
remainder =
modBy d m
in
sign ++ String.fromInt quotient ++ "." ++ decimalRep remainder d
The interesting part is handled by decimalRep remainder d, where 1 <= remainder < d. Let's develop an understanding for the problem that decimalRep needs to solve.
Decimal Notation
Decimal notation is a way of representing numbers using powers of 10. For e.g.
\[ 123.456 = 1 \times 10^2 + 2 \times 10^1 + 3 \times 10^0 + 4 \times 10^{-1} + 5 \times 10^{-2} + 6 \times 10^{-3} \]
As a result, it is easier to convert a fraction to a decimal when its denominator is a power of 10. For e.g.
\[ \frac{98765}{1000} = 98.765 \]
Multiplication by 1
Let r be any rational number. Then, r * 1 = r. In particular, notice that 10/10 = 1. So, r * 10/10 = r = 10r * 1/10. If r has numerator n and denominator d then r = 10n/d * 1/10. How can this help us? We can use this to get powers of 10 in the denominator to make it easier to extract the decimal digits. Let's look at a few examples:
Example 1: 1/2
\[ \begin{align} \frac{1}{2} &= \frac{1}{2} \times 1 \\ &= \frac{1}{2} \times \frac{10}{10} \\ &= \frac{10}{2} \times \frac{1}{10} \\ &= 5 \times \frac{1}{10} \\ &= \frac{5}{10} \\ &= 0.5 \end{align} \]
Example 2: 1/4
\[ \begin{align} \frac{1}{4} &= \frac{1}{4} \times 1 \\ &= \frac{1}{4} \times \frac{10}{10} \\ &= \frac{10}{4} \times \frac{1}{10} \\ &= 2 \frac{1}{2} \times \frac{1}{10} \\ &= (2 + \frac{1}{2}) \times \frac{1}{10} \\ &= \frac{2}{10} + 0.5 \times \frac{1}{10} \\ &= 0.2 + 0.05 \\ &= 0.25 \end{align} \]
Example 3: 1/8
\[ \begin{align} \frac{1}{8} &= \frac{1}{8} \times 1 \\ &= \frac{1}{8} \times \frac{10}{10} \\ &= \frac{10}{8} \times \frac{1}{10} \\ &= 1 \frac{1}{4} \times \frac{1}{10} \\ &= (1 + \frac{1}{4}) \times \frac{1}{10} \\ &= \frac{1}{10} + 0.25 \times \frac{1}{10} \\ &= 0.1 + 0.025 \\ &= 0.125 \end{align} \]
Example 4: 3/7
\[ \begin{align} \frac{3}{7} &= \frac{3}{7} \times 1 \\ &= \frac{3}{7} \times \frac{10}{10} \\ &= \frac{30}{7} \times \frac{1}{10} \\ &= 4 \frac{2}{7} \times \frac{1}{10} \\ &= (4 + \frac{2}{7}) \times \frac{1}{10} \\ &= 0.4 + \frac{2}{7} \times \frac{1}{10} \\ \end{align} \]
\[ \begin{align} \frac{2}{7} &= \frac{2}{7} \times 1 \\ &= \frac{2}{7} \times \frac{10}{10} \\ &= \frac{20}{7} \times \frac{1}{10} \\ &= 2 \frac{6}{7} \times \frac{1}{10} \\ &= (2 + \frac{6}{7}) \times \frac{1}{10} \\ &= 0.2 + \frac{6}{7} \times \frac{1}{10} \\ \end{align} \]
\[ \begin{align} \frac{6}{7} &= \frac{6}{7} \times 1 \\ &= \frac{6}{7} \times \frac{10}{10} \\ &= \frac{60}{7} \times \frac{1}{10} \\ &= 8 \frac{4}{7} \times \frac{1}{10} \\ &= (8 + \frac{4}{7}) \times \frac{1}{10} \\ &= 0.8 + \frac{4}{7} \times \frac{1}{10} \\ \end{align} \]
\[ \begin{align} \frac{4}{7} &= \frac{4}{7} \times 1 \\ &= \frac{4}{7} \times \frac{10}{10} \\ &= \frac{40}{7} \times \frac{1}{10} \\ &= 5 \frac{5}{7} \times \frac{1}{10} \\ &= (5 + \frac{5}{7}) \times \frac{1}{10} \\ &= 0.5 + \frac{5}{7} \times \frac{1}{10} \\ \end{align} \]
\[ \begin{align} \frac{5}{7} &= \frac{5}{7} \times 1 \\ &= \frac{5}{7} \times \frac{10}{10} \\ &= \frac{50}{7} \times \frac{1}{10} \\ &= 7 \frac{1}{7} \times \frac{1}{10} \\ &= (7 + \frac{1}{7}) \times \frac{1}{10} \\ &= 0.7 + \frac{1}{7} \times \frac{1}{10} \\ \end{align} \]
\[ \begin{align} \frac{1}{7} &= \frac{1}{7} \times 1 \\ &= \frac{1}{7} \times \frac{10}{10} \\ &= \frac{10}{7} \times \frac{1}{10} \\ &= 1 \frac{3}{7} \times \frac{1}{10} \\ &= (1 + \frac{3}{7}) \times \frac{1}{10} \\ &= 0.1 + \frac{3}{7} \times \frac{1}{10} \\ \end{align} \]
And, it will start to repeat. So,
\[ \begin{align} \frac{3}{7} &= 0.4 + \frac{2}{7} \times \frac{1}{10} \\ &= 0.4 + (0.2 + \frac{6}{7} \times \frac{1}{10}) \times \frac{1}{10} \\ &= 0.4 + (0.2 + (0.8 + \frac{4}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10} \\ &= 0.4 + (0.2 + (0.8 + (0.5 + \frac{5}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10} \\ &= 0.4 + (0.2 + (0.8 + (0.5 + (0.7 + \frac{1}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10} \\ &= 0.4 + (0.2 + (0.8 + (0.5 + (0.7 + (0.1 + \frac{3}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10} \\ &= 0.4 + 0.02 + (0.8 + (0.5 + (0.7 + (0.1 + \frac{3}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{100} \\ &= 0.4 + 0.02 + 0.008 + (0.5 + (0.7 + (0.1 + \frac{3}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{1000} \\ &= 0.4 + 0.02 + 0.008 + 0.0005 + (0.7 + (0.1 + \frac{3}{7} \times \frac{1}{10}) \times \frac{1}{10}) \times \frac{1}{10000} \\ &= 0.4 + 0.02 + 0.008 + 0.0005 + 0.00007 + (0.1 + \frac{3}{7} \times \frac{1}{10}) \times \frac{1}{100000} \\ &= 0.4 + 0.02 + 0.008 + 0.0005 + 0.00007 + 0.000001 + \frac{3}{7} \times \frac{1}{1000000} \\ &= 0.428571 + \frac{3}{7} \times \frac{1}{1000000} \\ \end{align} \]
Towards an Algorithm
Let's take a closer look at how we determined the decimal representation for 3/7.
| n | d | 10n | q | r | memo | terms |
|---|---|---|---|---|---|---|
| 3 | 7 | 30 | 4 | 2 | [ (3, (4, 2)) ] | [ (4, 2) ] |
| 2 | 7 | 20 | 2 | 6 | [ (2, (2, 6)), (3, (4, 2)) ] | [ (2, 6), (4, 2) ] |
| 6 | 7 | 60 | 8 | 4 | [ (6, (8, 4)), (2, (2, 6)), (3, (4, 2)) ] | [ (8, 4), (2, 6), (4, 2) ] |
| 4 | 7 | 40 | 5 | 5 | [ (4, (5, 5)), (6, (8, 4)), (2, (2, 6)), (3, (4, 2)) ] | [ (5, 5), (8, 4), (2, 6), (4, 2) ] |
| 5 | 7 | 50 | 7 | 1 | [ (5, (7, 1)), (4, (5, 5)), (6, (8, 4)), (2, (2, 6)), (3, (4, 2)) ] | [ (7, 1), (5, 5), (8, 4), (2, 6), (4, 2) ] |
| 1 | 7 | 10 | 1 | 3 | [ (1, (1, 3)), (5, (7, 1)), (4, (5, 5)), (6, (8, 4)), (2, (2, 6)), (3, (4, 2)) ] | [ (1, 3), (7, 1), (5, 5), (8, 4), (2, 6), (4, 2) ] |
| 3 | 7 | — | — | — | — | — |
where q = 10n div d and r = 10n mod d. We keep going until either (n, d) repeats or r = 0.
decimalRep
Based on the above analysis, here's an implementation for decimalRep that satisfies the requirements:
decimalRep : Int -> Int -> String
decimalRep n d =
decimalRepHelper n d [] Dict.empty
decimalRepHelper : Int -> Int -> List ( Int, Int ) -> Dict Int ( Int, Int ) -> String
decimalRepHelper n d terms memo =
case Dict.get n memo of
Just ( q, r ) ->
displayRepeating ( q, r ) terms ")"
Nothing ->
let
n10 =
n * 10
q =
n10 // d
r =
modBy d n10
in
if r == 0 then
displayTerminating (( q, r ) :: terms) ""
else
decimalRepHelper
r
d
(( q, r ) :: terms)
(Dict.insert n ( q, r ) memo)
displayTerminating : List ( Int, Int ) -> String -> String
displayTerminating terms output =
case terms of
[] ->
output
( q, _ ) :: rest ->
displayTerminating rest (String.fromInt q ++ output)
displayRepeating : ( Int, Int ) -> List ( Int, Int ) -> String -> String
displayRepeating marker terms output =
case terms of
[] ->
output
( q, r ) :: rest ->
let
s =
if ( q, r ) == marker then
"(" ++ String.fromInt q
else
String.fromInt q
in
displayRepeating marker rest (s ++ output)
decimalRepHelper, displayTerminating, and displayRepeating are all implemented using tail-recursion so they can be optimized into loops.
Unit Tests
new
test "both numerator and denominator are positive" <|
\_ ->
Rational.new 2 4
|> Maybe.map Rational.toString
|> Expect.equal (Just "1/2")
test "only numerator is positive" <|
\_ ->
Rational.new 2 -4
|> Maybe.map Rational.toString
|> Expect.equal (Just "-1/2")
test "only denominator is positive" <|
\_ ->
Rational.new -2 4
|> Maybe.map Rational.toString
|> Expect.equal (Just "-1/2")
test "both numerator and denominator are negative" <|
\_ ->
Rational.new -2 -4
|> Maybe.map Rational.toString
|> Expect.equal (Just "1/2")
Arithmetic
test "1/2 + 1/8" <|
\_ ->
Maybe.map2 Rational.add (Rational.new 1 2) (Rational.new 1 8)
|> Maybe.map Rational.toString
|> Expect.equal (Just "5/8")
test "1/2 - 1/8" <|
\_ ->
Maybe.map2 Rational.sub (Rational.new 1 2) (Rational.new 1 8)
|> Maybe.map Rational.toString
|> Expect.equal (Just "3/8")
test "1/2 * 1/8" <|
\_ ->
Maybe.map2 Rational.mul (Rational.new 1 2) (Rational.new 1 8)
|> Maybe.map Rational.toString
|> Expect.equal (Just "1/16")
test "1/2 / 1/8" <|
\_ ->
Maybe.map2 Rational.div (Rational.new 1 2) (Rational.new 1 8)
|> Maybe.map Rational.toString
|> Expect.equal (Just "4")
test "1/4 / 0" <|
\_ ->
Maybe.map2 Rational.div (Rational.new 1 4) (Rational.new 0 1)
|> Maybe.map Rational.toString
|> Expect.equal (Just "0")
Decimal Conversion
Terminating Decimals
test "1/2" <|
\_ ->
Rational.new 1 2
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.5")
test "-1/2" <|
\_ ->
Rational.new -1 2
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "-0.5")
test "5/2" <|
\_ ->
Rational.new 5 2
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "2.5")
test "1/4" <|
\_ ->
Rational.new 1 4
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.25")
test "1/5" <|
\_ ->
Rational.new 1 5
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.2")
test "1/8" <|
\_ ->
Rational.new 1 8
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.125")
Repeating Decimals
test "1/3" <|
\_ ->
Rational.new 1 3
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(3)")
test "2/3" <|
\_ ->
Rational.new 2 3
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(6)")
test "1/6" <|
\_ ->
Rational.new 1 6
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.1(6)")
test "5/6" <|
\_ ->
Rational.new 5 6
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.8(3)")
test "1/7" <|
\_ ->
Rational.new 1 7
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(142857)")
test "2/7" <|
\_ ->
Rational.new 2 7
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(285714)")
test "3/7" <|
\_ ->
Rational.new 3 7
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(428571)")
test "1/9" <|
\_ ->
Rational.new 1 9
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(1)")
test "2/9" <|
\_ ->
Rational.new 2 9
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(2)")
test "8/9" <|
\_ ->
Rational.new 8 9
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(8)")
test "7/12" <|
\_ ->
Rational.new 7 12
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.58(3)")
test "1/23" <|
\_ ->
Rational.new 1 23
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(0434782608695652173913)")
test "1/97" <|
\_ ->
Rational.new 1 97
|> Maybe.map Rational.toDecimalString
|> Expect.equal (Just "0.(010309278350515463917525773195876288659793814432989690721649484536082474226804123711340206185567)")
Resources
Evaluating Infix Expressions
When the user interacts with the calculator and presses certain buttons (0-9, ., +, -, ×, ÷), under the hood, they are actually building up a data structure that represents an infix expression. To evaluate that infix expression I use Dijkstra's Shunting Yard Algorithm to convert it into a postfix expression which is much easier to evaluate. The postfix expression is never explicitly returned since I evaluate it on the fly. As such, my evaluation function makes use of two stacks. Therefore, let's start with an implementation of a stack data structure before moving on to the star of the show.
Stack
A stack is a data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added is the first one to be removed. It operates like a stack of plates, where you can only add or remove plates from the top.
Public API
module Lib.Stack exposing
( Stack
, new
, isEmpty
, push, pop
)
-- Representation
type Stack a
-- Constructor
new : Stack
-- Query
isEmpty : Stack -> Bool
-- Modifiers
push : a -> Stack a -> Stack a
pop : Stack a -> Maybe ( a, Stack a )
Representation
I represent a stack using a list where the head of the list corresponds to the top of the stack.
type Stack a
= Stack (List a)
Constructor
The one constructor, new, creates an empty stack which is just an empty list.
new : Stack a
new =
Stack []
Query
A stack is empty if it's the empty list.
isEmpty : Stack a -> Bool
isEmpty (Stack xs) =
xs == []
Modifiers
The two main operations of a stack are push and pop.
push
It adds an element to the top of the stack.
push : a -> Stack a -> Stack a
push x (Stack xs) =
Stack (x :: xs)
pop
It removes and returns the element at the top of the stack. We have to take into account that the stack may be empty.
pop : Stack a -> Maybe ( a, Stack a )
pop (Stack xs) =
case xs of
[] ->
Nothing
x :: rest ->
Just ( x, Stack rest )
Resources
Dijkstra's Shunting Yard Algorithm
Algorithm
The following pseudocode describes an algorithm, based on Dijkstra's shunting yard algorithm, for evaluating infix expressions. It assumes that the infix expression has already been tokenized.
eval(tokens: List of Token) -> Rational or Error
-- Initialization
operands = Stack.empty()
operators = Stack.empty()
-- Process the tokens
for t in tokens do
if t is a number, n then
operands.push(n)
else if t is an operator, op1 then
-- Evaluate the dominant operators
while operators.isNotEmpty() do
op2 = operators.top()
if precendence(op2) >= precendence(op1) then
op2 = operators.pop()
evalBinOp(op2, operands)
else
break
end if
end while
operators.push(op1)
end if
end for
-- Process the operators
while operators.isNotEmpty() do
op = operators.pop()
evalBinOp(op, operands)
end while
-- Return the value
if operands.isEmpty() then
raise an error
end if
value = operands.pop()
if operands.isEmpty() then
return value
else
raise an error
end if
end
evalBinOp(op: Operator, operands: Stack of Rational) -> () or Error
if operands.isEmpty() then
raise an error
end if
b = operands.pop()
if operands.isEmpty() then
raise an error
end if
a = operands.pop()
if op is addition then
operands.push(a + b)
else if op is subtraction then
operands.push(a - b)
else if op is multiplication then
operands.push(a × b)
else if op is division then
operands.push(a ÷ b)
end if
end
Tokenization
The infix expression 1 + 9 - 17 × 3 ÷ 4 would be tokenized as follows:
[ Number (Rational.fromInt 1)
, Operand Add
, Number (Rational.fromInt 9)
, Operand Sub
, Number (Rational.fromInt 17)
, Operand Mul
, Number (Rational.fromInt 3)
, Operand Div
, Number (Rational.fromInt 2)
]
Precedence
The precendence of the supported operators are as follows:
| Operator | Precedence |
|---|---|
Add | 1 |
Sub | 1 |
Mul | 2 |
Div | 2 |
Add and Sub have the same level but lower precedence than Mul and Div. All the supported operators are left-associative so we don't have to deal with associativity. However, if we decide to add exponentiation, which is right-associative, then we'd have to start considering associativity.
The corresponding precedence function can be implemented as follows:
precedence : Operator -> Int
precedence op =
case op of
Add ->
1
Sub ->
1
Mul ->
2
Div ->
2
Examples
These examples are here to help you understand the algorithm.
Example 1
Input: 3
| Token | Action | Operands | Operators | Value |
|---|---|---|---|---|
3 | Push 3 to operands | [ 3 ] | [] | |
| None | Pop from operands | [] | [] | 3 |
Output: 3
Example 2
Input: 1 + 2
| Token | Action | Operands | Operators | Value | Comment |
|---|---|---|---|---|---|
1 | Push 1 to operands | [ 1 ] | [] | ||
+ | Push + to operators | [ 1 ] | [ + ] | ||
2 | Push 2 to operands | [ 2, 1 ] | [ + ] | ||
| None | Process + operator | [ 3 ] | [] | 1 + 2 | |
| None | Pop from operands | [] | [] | 3 |
Output: 3
Example 3
Input: 1 + 2 × 3
| Token | Action | Operands | Operators | Value | Comment |
|---|---|---|---|---|---|
1 | Push 1 to operands | [ 1 ] | [] | ||
+ | Push + to operators | [ 1 ] | [ + ] | ||
2 | Push 2 to operands | [ 2, 1 ] | [ + ] | ||
× | Push × to operators | [ 2, 1 ] | [ ×, + ] | ||
3 | Push 3 to operands | [ 3, 2, 1 ] | [ ×, + ] | ||
| None | Process × operator | [ 6, 1 ] | [ + ] | 2 × 3 | |
| None | Process + operator | [ 7 ] | [] | 1 + 6 | |
| None | Pop from operands | [] | [] | 7 |
Output: 7
Example 4
Input: 4 × 5 + 6
| Token | Action | Operands | Operators | Value | Comment |
|---|---|---|---|---|---|
4 | Push 4 to operands | [ 4 ] | [] | ||
× | Push × to operators | [ 4 ] | [ × ] | ||
5 | Push 5 to operands | [ 5, 4 ] | [ × ] | ||
+ | Process × operator | [ 20 ] | [] | 4 × 5 | |
+ | Push + to operators | [ 20 ] | [ + ] | ||
6 | Push 6 to operands | [ 6, 20 ] | [ + ] | ||
| None | Process + operator | [ 26 ] | [] | 20 + 6 | |
| None | Pop from operands | [] | [] | 26 |
Output: 26
Example 5
Input: 3 + 4 × 2 ÷ 4
| Token | Action | Operands | Operators | Value | Comment |
|---|---|---|---|---|---|
3 | Push 3 to operands | [ 3 ] | [] | ||
+ | Push + to operators | [ 3 ] | [ + ] | ||
4 | Push 4 to operands | [ 4, 3 ] | [ + ] | ||
× | Push × to operators | [ 4, 3 ] | [ ×, + ] | ||
2 | Push 2 to operands | [ 2, 4, 3 ] | [ ×, + ] | ||
÷ | Process × operator | [ 8, 3 ] | [ + ] | 4 × 2 | |
÷ | Push ÷ to operators | [ 8, 3 ] | [ ÷, + ] | ||
4 | Push 4 to operands | [ 4, 8, 3 ] | [ ÷, + ] | ||
| None | Process ÷ operator | [ 2, 3 ] | [ + ] | 8 ÷ 4 | |
| None | Process + operator | [ 5 ] | [] | 3 + 2 | |
| None | Pop from operands | [] | [] | 5 |
Output: 5
Translating the Algorithm to Elm
Preamble
module Data.Evaluator exposing (Answer, Error(..), eval)
import Data.Operator exposing (Operator(..))
import Data.Token exposing (Token(..))
import Lib.Rational as Rational exposing (Rational)
import Lib.Stack as Stack exposing (Stack)
type alias Answer =
Result Error Rational
type Error
= SyntaxError
eval : List Token -> Answer
eval tokens =
-- ...
When evaluating a given infix expression we can either get a syntax error or a rational number.
A syntax error, SyntaxError, is possible if tokens is illegally formed, for e.g.:
tokens |
|---|
[] |
[ Operator Add ] |
[ Number (Rational.fromInt 1), Operator Add ] |
[ Number (Rational.fromInt 1), Number (Rational.fromInt 2) ] |
Dealing with Mutation
The algorithm treats operands and operators as mutable stacks. Since Elm doesn't support mutable data structures we'd have to find another way to change the stacks as the program performs its steps. The typical way we simulate mutability is inputing and outputing a value of the same type. I stored all the global state together in one record type called State:
type alias State =
{ operands : Stack Rational
, operators : Stack Operator
}
To make State easier to work with and "mutate", I implemented the following helper functions:
pushOperand : Rational -> State -> Result Error State
pushOperand q state =
Ok { state | operands = Stack.push q state.operands }
popOperand : State -> Result Error ( Rational, State )
popOperand state =
case Stack.pop state.operands of
Just ( q, operands ) ->
Ok ( q, { state | operands = operands } )
Nothing ->
Err SyntaxError
pushOperator : Operator -> State -> Result Error State
pushOperator op state =
Ok { state | operators = Stack.push op state.operators }
popOperator : (Operator -> State -> Result Error State) -> (State -> Result Error State) -> State -> Result Error State
popOperator onOperator onEmpty state =
case Stack.pop state.operators of
Just ( op, operators ) ->
onOperator op { state | operators = operators }
Nothing ->
onEmpty state
Initialization
From the algorithm:
eval(tokens: List of Token) -> Rational or Error
-- Initialization
operands = Stack.empty()
operators = Stack.empty()
-- Process the tokens
for t in tokens do
-- ...
end for
-- Process the operators
-- Return the value
end
Translated to Elm:
eval : List Token -> Answer
eval tokens =
let
-- Initialization
state =
{ operands = Stack.new
, operators = Stack.new
}
in
-- Process the tokens
-- Process the operators
evalTokens tokens state
|> Result.andThen
(\{ operands, operators } ->
-- Return the value
)
Process the Tokens
From the algorithm:
-- Process the tokens
for t in tokens do
if t is a number, n then
operands.push(n)
else if t is an operator, op1 then
-- Evaluate the dominant operators
end if
end for
-- Process the operators
-- Return the value
Translated to Elm:
evalTokens : List Token -> State -> Result Error State
evalTokens tokens state =
case tokens of
[] ->
-- Process the operators
evalOperators state
token :: restTokens ->
evalToken token state
|> Result.andThen (evalTokens restTokens)
evalToken : Token -> State -> Result Error State
evalToken token state =
case token of
Number n ->
pushOperand n state
Operator op ->
-- Evaluate the dominant operators
evalDominantOperators op state
Evaluate the Dominant Operators
From the algorithm:
-- Evaluate the dominant operators
while operators.isNotEmpty() do
op2 = operators.top()
if precendence(op2) >= precendence(op1) then
op2 = operators.pop()
evalBinOp(op2, operands)
else
break
end if
end while
operators.push(op1)
And, evalBinOp from the algorithm:
evalBinOp(op: Operator, operands: Stack of Rational) -> () or Error
if operands.isEmpty() then
raise an error
end if
b = operands.pop()
if operands.isEmpty() then
raise an error
end if
a = operands.pop()
if op is addition then
operands.push(a + b)
else if op is subtraction then
operands.push(a - b)
else if op is multiplication then
operands.push(a × b)
else if op is division then
operands.push(a ÷ b)
end if
end
Translated to Elm:
evalDominantOperators : Operator -> State -> Result Error State
evalDominantOperators op1 state0 =
popOperator
(\op2 state1 ->
if precedence op2 >= precedence op1 then
evalOperation op2 state1
|> Result.andThen (evalDominantOperators op1)
else
pushOperator op1 state0
)
(pushOperator op1)
state0
evalOperation : Operator -> State -> Result Error State
evalOperation op state0 =
popOperand state0
|> Result.andThen
(\( right, state1 ) ->
popOperand state1
|> Result.andThen
(\( left, state2 ) ->
evalBinOp op left right state2
)
)
evalBinOp : Operator -> Rational -> Rational -> State -> Result Error State
evalBinOp op a b =
pushOperand <|
case op of
Add ->
Rational.add a b
Sub ->
Rational.sub a b
Mul ->
Rational.mul a b
Div ->
Rational.div a b
Process the Operators
From the algorithm:
-- Process the operators
while operators.isNotEmpty() do
op = operators.pop()
evalBinOp(op, operands)
end while
Translated to Elm:
evalOperators : State -> Result Error State
evalOperators state0 =
popOperator
(\op state1 ->
evalOperation op state1
|> Result.andThen evalOperators
)
(\state1 -> Ok state1)
state0
This can be simplified to:
evalOperators : State -> Result Error State
evalOperators =
popOperator
(\op -> evalOperation op >> Result.andThen evalOperators)
Ok
Return the Value
From the algorithm:
-- Return the value
if operands.isEmpty() then
raise an error
end if
value = operands.pop()
if operands.isEmpty() then
return value
else
raise an error
end if
Translated to Elm:
case ( Stack.pop operands, Stack.isEmpty operators ) of
( Just ( value, newOperands ), True ) ->
if Stack.isEmpty newOperands then
Ok value
else
Err SyntaxError
_ ->
Err SyntaxError
All Together
module Data.Evaluator exposing (Answer, Error(..), eval)
import Data.Operator exposing (Operator(..))
import Data.Token exposing (Token(..))
import Lib.Rational as Rational exposing (Rational)
import Lib.Stack as Stack exposing (Stack)
type alias Answer =
Result Error Rational
type Error
= SyntaxError
type alias State =
{ operands : Stack Rational
, operators : Stack Operator
}
eval : List Token -> Answer
eval tokens =
let
state =
{ operands = Stack.new
, operators = Stack.new
}
in
evalTokens tokens state
|> Result.andThen
(\{ operands, operators } ->
case ( Stack.pop operands, Stack.isEmpty operators ) of
( Just ( value, newOperands ), True ) ->
if Stack.isEmpty newOperands then
Ok value
else
Err SyntaxError
_ ->
Err SyntaxError
)
evalTokens : List Token -> State -> Result Error State
evalTokens tokens state =
case tokens of
[] ->
evalOperators state
token :: restTokens ->
evalToken token state
|> Result.andThen (evalTokens restTokens)
evalToken : Token -> State -> Result Error State
evalToken token state =
case token of
Number n ->
pushOperand n state
Operator op ->
evalDominantOperators op state
evalDominantOperators : Operator -> State -> Result Error State
evalDominantOperators op1 state0 =
popOperator
(\op2 state1 ->
if precedence op2 >= precedence op1 then
evalOperation op2 state1
|> Result.andThen (evalDominantOperators op1)
else
pushOperator op1 state0
)
(pushOperator op1)
state0
evalOperators : State -> Result Error State
evalOperators =
popOperator
(\op -> evalOperation op >> Result.andThen evalOperators)
Ok
evalOperation : Operator -> State -> Result Error State
evalOperation op state0 =
popOperand state0
|> Result.andThen
(\( right, state1 ) ->
popOperand state1
|> Result.andThen
(\( left, state2 ) ->
evalBinOp op left right state2
)
)
evalBinOp : Operator -> Rational -> Rational -> State -> Result Error State
evalBinOp op a b =
pushOperand <|
case op of
Add ->
Rational.add a b
Sub ->
Rational.sub a b
Mul ->
Rational.mul a b
Div ->
Rational.div a b
pushOperand : Rational -> State -> Result Error State
pushOperand q state =
Ok { state | operands = Stack.push q state.operands }
popOperand : State -> Result Error ( Rational, State )
popOperand state =
case Stack.pop state.operands of
Just ( q, operands ) ->
Ok ( q, { state | operands = operands } )
Nothing ->
Err SyntaxError
pushOperator : Operator -> State -> Result Error State
pushOperator op state =
Ok { state | operators = Stack.push op state.operators }
popOperator : (Operator -> State -> Result Error State) -> (State -> Result Error State) -> State -> Result Error State
popOperator onOperator onEmpty state =
case Stack.pop state.operators of
Just ( op, operators ) ->
onOperator op { state | operators = operators }
Nothing ->
onEmpty state
precedence : Operator -> Int
precedence op =
case op of
Add ->
1
Sub ->
1
Mul ->
2
Div ->
2
Resources
- src/Data/Evaluator.elm
- src/Data/Token.elm
- src/Data/Operator.elm
- src/Lib/Stack.elm
- src/Lib/Rational.elm
Unit Tests
Simple Expressions
test "1" <|
\_ ->
expectEval
[ intT 1 ]
(int 1)
test "1+2" <|
\_ ->
expectEval
[ intT 1, operatorT Add, intT 2 ]
(int 3)
test "6-1" <|
\_ ->
expectEval
[ intT 6, operatorT Sub, intT 1 ]
(int 5)
test "2*5" <|
\_ ->
expectEval
[ intT 2, operatorT Mul, intT 5 ]
(int 10)
test "10/2" <|
\_ ->
expectEval
[ intT 10, operatorT Div, intT 2 ]
(int 5)
test "5/2" <|
\_ ->
expectEval
[ intT 5, operatorT Div, intT 2 ]
(rational 5 2)
test "1/0" <|
\_ ->
expectEval
[ intT 1, operatorT Div, intT 0 ]
(int 0)
Operator Precedence
test "2+3-4" <|
\_ ->
expectEval
[ intT 2, operatorT Add, intT 3, operatorT Sub, intT 4 ]
(int 1)
test "2-3+4" <|
\_ ->
expectEval
[ intT 2, operatorT Sub, intT 3, operatorT Add, intT 4 ]
(int 3)
test "1+2*3" <|
\_ ->
expectEval
[ intT 1, operatorT Add, intT 2, operatorT Mul, intT 3 ]
(int 7)
test "1+3/3" <|
\_ ->
expectEval
[ intT 1, operatorT Add, intT 3, operatorT Div, intT 3 ]
(int 2)
test "1+2-5*8+6-10*3" <|
\_ ->
expectEval
[ intT 1
, operatorT Add
, intT 2
, operatorT Sub
, intT 5
, operatorT Mul
, intT 8
, operatorT Add
, intT 6
, operatorT Sub
, intT 10
, operatorT Mul
, intT 3
]
(int -61)
Helpers
expectEval : List Token -> Rational -> Expectation
expectEval tokens expectedRational =
case E.eval tokens of
Ok actualRational ->
Expect.equal expectedRational actualRational
Err _ ->
Expect.fail "eval failed"
int : Int -> Rational
int =
Rational.fromInt
rational : Int -> Int -> Rational
rational n d =
Rational.new n d
|> Maybe.withDefault Rational.zero
intT : Int -> Token
intT =
Token.Number << int
operatorT : Operator -> Token
operatorT =
Token.Operator
Resources
Calculator
The logical representation of the calculator. It has an internal data structure that it uses to keep track of the infix expression that the user builds one key press at a time.
Public API
module Data.Calculator exposing
( Calculator
, new
, press
, Output, toOutput
)
import Data.Key exposing (Key)
-- Representation
type Calculator
-- Constructor
new : Calculator
-- Update
press : Key -> Calculator -> Calculator
-- Conversion
type alias Output =
{ line1 : String
, line2 : String
}
toOutput : Calculator -> Output
Tokenizing Input
The calculator tokenizes the user's input. This suggests the use of a finite-state machine to help with the tokenization.
Why?
Well, lexical analyzers use regular expressions to tokenize a string of characters. Regular expressions are equivalent to finite-state machines. And, rather than a string of characters we have a list of key presses. So the idea is to have the calculator act like a lexical analyzer and use a finite-state machine to tokenize the list of key presses.
The Finite-State Machine
It has 5 states. The start state is called Start and it has one final state called Answer. The other states are called Left, Partial, and Right. I represented it as follows:
import Data.Evaluator as E
import Data.Operator exposing (Operator)
import Data.Token exposing (Token)
type Calculator
= Calculator State
type State
= Start
| Left Decimal
| Partial (List Token) Operator
| Right (List Token) Operator Decimal
| Answer (List Token) E.Answer
Left represents the situation when the user is entering their first, leftmost, number.
Partial represents the situation when the user just finished entering a number and they pressed an operator key.
Right represents the situation when the user is entering the second number for the operator.
Notice that the Answer state keeps track of the full tokenized input as well as the answer produced by the evaluator.
What's Decimal?
It's a type to help me tokenize decimal numbers.
type Decimal
= Whole Int
| Fractional Int Int Int
Let's consider an example where the user is entering the decimal number 123.456.
| Key Pressed | Decimal | Comment |
|---|---|---|
Digit One | Whole 1 | Digit.toInt One = 1 |
Digit Two | Whole 12 | 1 * 10 + Digit.toInt Two = 12 |
Digit Three | Whole 123 | 12 * 10 + Digit.toInt Three = 123 |
Dot | Fractional 123 0 1 | 123 + 0/1 = 123 |
Digit Four | Fractional 123 4 10 | 123 + 4/10 = 123.4 |
Digit Five | Fractional 123 45 100 | 123 + 45/100 = 123.45 |
Digit Six | Fractional 123 456 1000 | 123 + 456/1000 = 123.456 |
If Whole 123 and Fractional 123 0 1 represent the same number then why change the representation when a Dot is pressed?
- The pressing of the
Dotsignals that the user is about to enter the fractional part of the number so it makes sense to initialize everything we'd need to accept the fractional part. Whole 123andFractional 123 0 1are displayed differently in line 2 of the calculator's display.Whole 123is displayed as123butFractional 123 0 1is displayed as123., i.e. it ends with a decimal point.
new
new : Calculator
new =
Calculator Start
Naturally, the calculator starts off in the Start state.
press
As the user presses keys the calculator should transition between states based on its current state and the key that was pressed. So, for each state, we have to figure out what to do for each key that could be pressed.
Recall Key:
type Key
= AC
| Dot
| Equal
| Digit Digit
| Operator Operator
Recall Digit:
type Digit
= Zero
| One
| Two
| Three
| Four
| Five
| Six
| Seven
| Eight
| Nine
Recall Operator:
type Operator
= Add
| Sub
| Mul
| Div
And, this is how press is implemented:
import Data.Digit as Digit
import Data.Evaluator as E
import Data.Key exposing (Key(..))
import Data.Operator as Operator exposing (Operator)
import Data.Token as Token exposing (Token)
import Lib.Rational as Rational exposing (Rational)
press : Key -> Calculator -> Calculator
press key (Calculator state) =
Calculator <| pressHelper key state
pressHelper : Key -> State -> State
pressHelper key state =
case state of
Start ->
case key of
AC ->
Start
Digit digit ->
Left <| Whole <| Digit.toInt digit
Operator _ ->
Start
Dot ->
Left <| Fractional 0 0 1
Equal ->
Start
Left n ->
case key of
AC ->
Start
Digit digit ->
let
d =
Digit.toInt digit
in
case n of
Whole w ->
Left <| Whole <| w * 10 + d
Fractional w f p ->
Left <| Fractional w (f * 10 + d) (p * 10)
Operator op ->
Partial [ Token.Number <| toRational n ] op
Dot ->
case n of
Whole w ->
Left <| Fractional w 0 1
Fractional _ _ _ ->
Left n
Equal ->
let
r =
toRational n
in
Answer [ Token.Number r ] <| Ok r
Partial tokens op ->
case key of
AC ->
Start
Digit digit ->
Right tokens op <| Whole <| Digit.toInt digit
Operator newOp ->
Partial tokens newOp
Dot ->
Right tokens op <| Fractional 0 0 1
Equal ->
Answer tokens <| eval tokens
Right tokens op n ->
case key of
AC ->
Start
Digit digit ->
let
d =
Digit.toInt digit
in
case n of
Whole w ->
Right tokens op <| Whole <| w * 10 + d
Fractional w f p ->
Right tokens op <| Fractional w (f * 10 + d) (p * 10)
Operator newOp ->
let
newTokens =
Token.Number (toRational n) :: Token.Operator op :: tokens
in
Partial newTokens newOp
Dot ->
case n of
Whole w ->
Right tokens op <| Fractional w 0 1
Fractional _ _ _ ->
Right tokens op n
Equal ->
let
newTokens =
Token.Number (toRational n) :: Token.Operator op :: tokens
in
Answer newTokens <| eval newTokens
Answer _ answer ->
case key of
AC ->
Start
Digit digit ->
Left <| Whole <| Digit.toInt digit
Operator op ->
case answer of
Ok r ->
Partial [ Token.Number r ] op
Err _ ->
state
Dot ->
Left <| Fractional 0 0 1
Equal ->
state
eval : List Token -> E.Answer
eval =
E.eval << List.reverse
Displaying Output
The calculator could be in one of 5 states. So, for each state we have to stringify the data that's available and determine within which lines to display them.
type alias Output =
{ line1 : String
, line2 : String
}
toOutput : Calculator -> Output
toOutput (Calculator state) =
case state of
Start ->
Output "" "0"
Left n ->
let
line1 =
Rational.toDecimalString <| toRational n
line2 =
toPaddedDecimalString n
in
Output line1 line2
Partial tokens op ->
let
line1 =
toExpr tokens ++ line2
line2 =
Operator.toString op
in
Output line1 line2
Right tokens op n ->
let
line1 =
toExpr tokens ++ Operator.toString op ++ right
right =
Rational.toDecimalString <| toRational n
line2 =
toPaddedDecimalString n
in
Output line1 line2
Answer tokens answer ->
let
line1 =
toExpr tokens ++ "=" ++ line2
line2 =
case answer of
Ok r ->
Rational.toDecimalString r
Err _ ->
"TODO: Display an appropriate error message."
in
Output line1 line2
toPaddedDecimalString : Decimal -> String
toPaddedDecimalString n =
case n of
Whole w ->
String.fromInt w
Fractional w f p ->
String.concat
[ String.fromInt w
, "."
, if f == 0 && p == 1 then
""
else
String.padLeft
(String.length (String.fromInt p) - 1)
'0'
(String.fromInt f)
]
toExpr : List Token -> String
toExpr =
String.concat << List.map Token.toString << List.reverse
toRational : Decimal -> Rational
toRational n =
case n of
Whole w ->
Rational.fromInt w
Fractional w f p ->
Maybe.map2 Rational.add (Rational.new w 1) (Rational.new f p)
|> Maybe.withDefault Rational.zero
toPaddedDecimalString
When the user enters trailing zeros after the decimal point we want to display that in line 2 of the display.
| Decimal | String |
|---|---|
Fractional 0 0 1 | "0." |
Fractional 0 0 1000 | "0.000" |
Fractional 0 500 1000000 | "0.000500" |
Unit Tests
press
describe "when nothing has been entered" <|
let
calculator =
Calculator.new
in
[ test "pressing AC" <|
\_ ->
calculator
|> Calculator.press AC
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
, test "pressing a digit" <|
\_ ->
calculator
|> Calculator.press (Digit One)
|> Calculator.toOutput
|> Expect.equal { line1 = "1", line2 = "1" }
, test "pressing an operator" <|
\_ ->
calculator
|> Calculator.press (Operator Add)
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
, test "pressing dot" <|
\_ ->
calculator
|> Calculator.press Dot
|> Calculator.toOutput
|> Expect.equal { line1 = "0", line2 = "0." }
, test "pressing =" <|
\_ ->
calculator
|> Calculator.press Equal
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
]
describe "when a number has been entered" <|
let
calculator =
Calculator.new
|> Calculator.press (Digit One)
|> Calculator.press (Digit Two)
in
[ test "pressing AC" <|
\_ ->
calculator
|> Calculator.press AC
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
, test "pressing a digit" <|
\_ ->
calculator
|> Calculator.press (Digit Three)
|> Calculator.toOutput
|> Expect.equal { line1 = "123", line2 = "123" }
, test "pressing an operator" <|
\_ ->
calculator
|> Calculator.press (Operator Add)
|> Calculator.toOutput
|> Expect.equal { line1 = "12+", line2 = "+" }
, test "pressing dot" <|
\_ ->
calculator
|> Calculator.press Dot
|> Calculator.toOutput
|> Expect.equal { line1 = "12", line2 = "12." }
, test "pressing =" <|
\_ ->
calculator
|> Calculator.press Equal
|> Calculator.toOutput
|> Expect.equal { line1 = "12=12", line2 = "12" }
]
describe "when a number and operator has been entered" <|
let
calculator =
Calculator.new
|> Calculator.press (Digit One)
|> Calculator.press (Digit Two)
|> Calculator.press (Operator Add)
in
[ test "pressing AC" <|
\_ ->
calculator
|> Calculator.press AC
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
, test "pressing a digit" <|
\_ ->
calculator
|> Calculator.press (Digit Three)
|> Calculator.toOutput
|> Expect.equal { line1 = "12+3", line2 = "3" }
, test "pressing an operator" <|
\_ ->
calculator
|> Calculator.press (Operator Sub)
|> Calculator.toOutput
|> Expect.equal { line1 = "12-", line2 = "-" }
, test "pressing dot" <|
\_ ->
calculator
|> Calculator.press Dot
|> Calculator.toOutput
|> Expect.equal { line1 = "12+0", line2 = "0." }
, test "pressing =" <|
\_ ->
calculator
|> Calculator.press Equal
|> Calculator.toOutput
|> Expect.equal { line1 = "12=12", line2 = "12" }
]
describe "when a complete expression has been entered" <|
let
calculator =
Calculator.new
|> Calculator.press (Digit One)
|> Calculator.press (Digit Two)
|> Calculator.press (Operator Add)
|> Calculator.press (Digit Three)
|> Calculator.press (Operator Sub)
|> Calculator.press (Digit Four)
in
[ test "pressing AC" <|
\_ ->
calculator
|> Calculator.press AC
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
, test "pressing a digit" <|
\_ ->
calculator
|> Calculator.press (Digit Five)
|> Calculator.toOutput
|> Expect.equal { line1 = "12+3-45", line2 = "45" }
, test "pressing an operator" <|
\_ ->
calculator
|> Calculator.press (Operator Add)
|> Calculator.toOutput
|> Expect.equal { line1 = "12+3-4+", line2 = "+" }
, test "pressing dot" <|
\_ ->
calculator
|> Calculator.press Dot
|> Calculator.toOutput
|> Expect.equal { line1 = "12+3-4", line2 = "4." }
, test "pressing =" <|
\_ ->
calculator
|> Calculator.press Equal
|> Calculator.toOutput
|> Expect.equal { line1 = "12+3-4=11", line2 = "11" }
]
describe "when an answer is given" <|
let
calculator =
Calculator.new
|> Calculator.press (Digit One)
|> Calculator.press (Digit Two)
|> Calculator.press (Operator Add)
|> Calculator.press (Digit Three)
|> Calculator.press (Operator Sub)
|> Calculator.press (Digit Four)
|> Calculator.press Equal
in
[ test "pressing AC" <|
\_ ->
calculator
|> Calculator.press AC
|> Calculator.toOutput
|> Expect.equal { line1 = "", line2 = "0" }
, test "pressing a digit" <|
\_ ->
calculator
|> Calculator.press (Digit Nine)
|> Calculator.toOutput
|> Expect.equal { line1 = "9", line2 = "9" }
, test "pressing an operator" <|
\_ ->
calculator
|> Calculator.press (Operator Add)
|> Calculator.toOutput
|> Expect.equal { line1 = "11+", line2 = "+" }
, test "pressing dot" <|
\_ ->
calculator
|> Calculator.press Dot
|> Calculator.toOutput
|> Expect.equal { line1 = "0", line2 = "0." }
, test "pressing =" <|
\_ ->
calculator
|> Calculator.press Equal
|> Calculator.toOutput
|> Expect.equal { line1 = "12+3-4=11", line2 = "11" }
]
Decimal Input
test "leading zeros are preserved" <|
\_ ->
let
calculator =
Calculator.new
|> Calculator.press Dot
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Zero)
in
calculator
|> Calculator.toOutput
|> Expect.equal { line1 = "0", line2 = "0.000" }
test "trailing zeros are preserved" <|
\_ ->
let
calculator =
Calculator.new
|> Calculator.press Dot
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Five)
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Zero)
|> Calculator.press (Digit Zero)
in
calculator
|> Calculator.toOutput
|> Expect.equal { line1 = "0.0005", line2 = "0.0005000" }
Operator Precedence
test "multiplication is done before addition" <|
\_ ->
let
calculator =
Calculator.new
|> Calculator.press (Digit One)
|> Calculator.press (Operator Add)
|> Calculator.press (Digit Two)
|> Calculator.press (Operator Mul)
|> Calculator.press (Digit Three)
|> Calculator.press Equal
in
calculator
|> Calculator.toOutput
|> Expect.equal { line1 = "1+2×3=7", line2 = "7" }
Negative Division
test "negative divided by positive" <|
\_ ->
let
calculator =
Calculator.new
|> Calculator.press (Digit One)
|> Calculator.press (Operator Sub)
|> Calculator.press (Digit Two)
|> Calculator.press Equal
|> Calculator.press (Operator Div)
|> Calculator.press (Digit Three)
|> Calculator.press Equal
in
calculator
|> Calculator.toOutput
|> Expect.equal { line1 = "-1÷3=-0.(3)", line2 = "-0.(3)" }
Resources
UI + Application Logic
The UI is encapsulated within the View.Page module. The application logic is encapsulated within the Data.Calculator module. They come together in Main to form the complete application.
module Main exposing (main)
import Browser
import Data.Calculator as Calculator exposing (Calculator)
import Data.Key exposing (Key)
import Html as H
import View.Page as Page
main : Program () Model Msg
main =
Browser.sandbox
{ init = init
, view = view
, update = update
}
-- MODEL
type alias Model =
{ calculator : Calculator
}
init : Model
init =
{ calculator = Calculator.new
}
-- UPDATE
type Msg
= Clicked Key
update : Msg -> Model -> Model
update msg model =
case msg of
Clicked key ->
{ model | calculator = Calculator.press key model.calculator }
-- VIEW
view : Model -> H.Html Msg
view { calculator } =
let
{ line1, line2 } =
Calculator.toOutput calculator
in
Page.view
{ calculator =
{ line1 = line1
, line2 = line2
, onClick = Clicked
}
, attribution =
{ name = "Dwayne Crooks"
, title = "Dwayne's GitHub profile"
, url = "https://github.com/dwayne"
}
}
Resources
Conclusion
I touched on a large variety of ideas in the tutorial and glossed over a lot of stuff. If you felt overwhelmed then that's completely understandable. The tutorial wasn't designed to spoon-feed you information. It was merely written to show you how I approach the task of building a non-trivial web application with Elm so that the end result is reliable, maintainable, and testable. Now that you've been exposed to these ideas I hope you take the time to reflect on your own approach to web application development and see how it changes the way you think about Elm and web application development in general.
Key Takeways
- The user interface (UI) and the application logic can be developed and tested independently of each other.
- The UI can be implemented to completion within a frontend workshop environment long before it needs to be translated to
elm/html. - Figuring out how to structure your HTML, write your CSS rules, and script your interactive JavaScript logic is still the hard part of web development but once you figure out how to do it the translation to Elm is typically a straightforward process.
elm/htmlis the final technology within which your UI will be written but it doesn't mean you have to start there. - Elm doesn't prevent you from thinking in terms of components. In fact, the Elm language has excellent features to support component driven UI development.
- Component driven UI development does NOT lead to nested TEA. They are entirely distinct concepts and one does NOT imply the other. What Evan talks about when he talks about components is separate from component driven UI development.
- Elm supports domain-driven development and turns it into a delightful experience. And, that last part is not opinionated at all. 😉
Thank you for taking your time to read the tutorial. I hope it was worthwhile for you.
Support
Do you have any questions? Is there something you need me to clarify? Is there a tutorial you'd like me to write? Do you have any feedback?
You can reach me at author at elmwithdwayne dot dev.
Where to Find Me?
I curate everything I'm doing at Elm with Dwayne, I write a lot about Elm on my blog, and I recently started a newsletter.