Bitwise and List

Allergies
Allergies in Elm 
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.

6th Nov 2024 · Found it useful?

Other Approaches to Allergies in Elm

Other ways our community solved this exercise
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
Bitwise and Dict

Use the key in a Dict to represent the bit position of the allergy. 

toList : Int -> List Allergy
toList score =
  [ 1, 2, 4, 8, 16, 32, 64, 128 ]
  |> List.filterMap ( \allergenInt -> intToAllergen (Bitwise.and score allergenInt))
Bitwise and case expression

Use a case expression to return the bit position of the allergy. 

allergiesAndScores = [AllergyAndScore Eggs 1, AllergyAndScore Peanuts 2, AllergyAndScore Shellfish 3, AllergyAndScore Strawberries 4, AllergyAndScore Tomatoes 5, AllergyAndScore Chocolate 6, AllergyAndScore Pollen 7, AllergyAndScore Cats 8]

toList : Int -> List Allergy
toList score =
  allergiesAndScores
    |> List.map (\{ bitPosition, allergy } -> ( 2 ^ (bitPosition - 1), allergy ))
    |> List.filter (\( s, _ ) -> Bitwise.and s score > 0)
    |> List.map Tuple.second
Bitwise, List and type alias

Use a type alias to represent the bit position of the allergy.