Visit the allergies exercise on Exercism to read the full instructions and download the exercise files.
Dig Deeper
Bitwise and List
Bitwise and List
allergies : List Allergy
allergies =
[ Eggs
, Peanuts
, Shellfish
, Strawberries
, Tomatoes
, Chocolate
, Pollen
, Cats
]
toList : Int -> List Allergy
toList score =
allergies
|> List.indexedMap (\i allergy -> ( 2 ^ i, allergy ))
|> List.filter (\( allergyScore, _ ) -> Bitwise.and allergyScore score > 0)
|> List.map Tuple.second
isAllergicTo : Allergy -> Int -> Bool
isAllergicTo allergy score =
toList score |> List.member allergy
In this approach
This approach implicitly uses the index of an item in a list to represent the bit position (minus one) for the allergy score.
List.indexedMap is used to map the list and provide the index of each item, it retains the Allergy and adds the bit mask in a tuple.
List.filter then filters out any Allergy in the list where the bit mask doesn’t match the score using Bitwise.and.
List.map and Tuple.second then map the filtered list from Tuple back to Allergy.
You can see the Bitwise and List solution on exercism.
When to use this approach?
This code is idiomatic in Elm and is concise.
It is probably the solution many Elm developers would naturally end up with first.
This approach does not fully embrace the domain concept of using bit positions in the allergy score to represent a list of Allergy.
It is relatively easy to work out what the code is doing, but it is not as easy to guess why it is doing it, you have to look at the exercise instructions to understand.
Ideally the code should communicate its meaning to you.
toList is a relatively expensive operation, iterating the allergies three times, or O(3n).
The first is to add the index, the second is to filter and the third is to map.
We can’t easily use List.foldr to avoid this, as it doesn’t provide the list index, and there is no indexedFoldr function available from the core libraries.
You could however use (index, list) for the accumulator in List.foldr to keep track of the index, at the expense of a little extra complexity.
isAllergicTo adds another iteration over the result of toList, making it more expensive.
However the initial allergies list is known and of small length, so for this exercise we should not try to prematurely optimise.
The compiler does not guarantee that the allergies list contains all the Allergy types.
You can use the type iterator pattern or use the no missing type constructor rule in Elm Review to fix this.
This approach guarantees all bit positions are valid, unless the number of allergies becomes too big, as Javascript (Elm’s compilation target) bitwise operators only operate on 32 bit integers.
This approach also guarantees that all bit positions are sequential.
This is potentially useful, but means that if there was ever a need for non sequential bit positions, we would have to refactor.
Bitwise and Dict
Bitwise and Dict
import Dict exposing (Dict)
allergies : Dict Int Allergy
allergies =
Dict.fromList
[ (1, Eggs)
, (2, Peanuts)
, (3, Shellfish)
, (4, Strawberries)
, (5, Tomatoes)
, (6, Chocolate)
, (7, Pollen)
, (8, Cats)
]
toList : Int -> List Allergy
toList score =
Dict.foldr (\key value list -> if Bitwise.and (2 ^ (key - 1)) score > 0 then (value :: list) else list) [] allergies
isAllergicTo : Allergy -> Int -> Bool
isAllergicTo allergy score =
toList score |> List.member allergy
In this approach
This approach explicitly uses the key of the Dict to represent the bit position of an Allergy.
Dict.foldr is used to create a list of Allergy, using Bitwise.and to match the allergy value with the score.
You can see a variation of a Bitwise and Dict solution on Exercism.
When to use this approach?
This code is idiomatic in Elm and is better at embracing the concept of using bit positions in the allergy score to represent a list of Allergy.
isAllergicTo is a slightly expensive operation, iterating the allergies dict once to make a list, and that list is iterated to match the allergy.
It is faster than the Bitwise and List approach.
However allergies is known and of very small size, so for this exercise we should not try to prematurely optimise.
The compiler does not guarantee that the allergies dict contains all the Allergy types.
You can use the type iterator pattern to fix this.
This approach does not guarantee that all bit positions are valid.
This approach doesn’t guarantee that all bit positions are sequential.
This is potentially useful, and means that if there was ever a need for non sequential bit positions, we could support it, but it does also make it easier to make a mistake if the bit positions are required to be sequential.
Bitwise and case expression
Bitwise and case expression
intToAllergen : Int -> Maybe Allergy
intToAllergen x =
case x of
1 ->
Just Eggs
2 ->
Just Peanuts
4 ->
Just Shellfish
8 ->
Just Strawberries
16 ->
Just Tomatoes
32 ->
Just Chocolate
64 ->
Just Pollen
128 ->
Just Cats
_ ->
Nothing
toList : Int -> List Allergy
toList score =
[ 1, 2, 4, 8, 16, 32, 64, 128 ]
|> List.filterMap ( \allergenInt -> intToAllergen (Bitwise.and score allergenInt))
isAllergicTo : Allergy -> Int -> Bool
isAllergicTo allergy score =
toList score |> List.member allergy
In this approach
This approach uses case expressions to represent a bit mask for the allergy.
A hard coded list of all the possible allergy values is created.
List.filterMap is used to filter and map the list.
It converts the allergy values to their matching Allergy or filters them out by returning Nothing.
You can see a variation of a Bitwise and case expression solution on Exercism.
When to use this approach?
This is not as concise as some other solutions, but the code is all very simple and easy to read.
It is the fastest solution of the different approaches.
This approach is better at embracing the concept of using bit positions in the allergy score to represent a list of Allergy, using the bit masks.
The bit masks (1, 2, 4 …) are duplicated once, which most people would say is Ok (people commonly refactor code when it is duplicated 3 times or more).
toList is fast, iterating the allergies just once, or O(n).
You can add an inverse of the intToAllergen function and use it in isAllergicTo, which would make the function as fast as it can be (O(1)).
However, this results in another duplication of the allergy values (1, 2, 4, …).
Optimising for speed usually means unoptimising something else.
The compiler does not guarantee that the intToAllergen function or the hard coded list of allergy values contains all the possible values.
This approach does not guarantee that all bit masks are valid, although you could use List.range and List.map to improve this.
This approach doesn’t guarantee that all bit masks are sequential.
This is potentially useful, and means that if there was ever a need for non sequential bit positions, we could support it, but it does also make it easier to make a mistake if the bit positions are required to be sequential.
Source: Exercism elm/allergies