3
\$\begingroup\$

I'm looking to generate a list of powers in Elm, up to a certain limit. I've written the following tests:

        [ test "works for negative limit" <| \_ -> equal (powers 2 -5) (Ok [])
        , test "works for 2 up to 63" <| \_ -> equal (powers 2 63) (Ok [1, 2, 4, 8, 16, 32])
        , test "works for 2 up to 64" <| \_ -> equal (powers 2 63) (Ok [1, 2, 4, 8, 16, 32])
        , test "works for 3 up to 81" <| \_ -> equal (powers 3 81) (Ok [1, 3, 9, 27, 81])
        , test "rejects negative bases" <| \_ -> equal (powers -2 63) (Err "negative base")
        ]

I have a solution that I'm not happy with because it seems pretty long. Now I know that when doing these kinds of things in the functional style, we generally use tail recursion (which is no problem). But as I am building up the list from small numbers to large numbers (e.g., 1 2 4 8 16 32 ...) I could keep appending to the accumulated list, but this is much slower than using prepend (::). So... I decided to prepend and then reverse at the very end:

powers base limit =
  if base < 0 then
    Err "negative base"
  else
    let
      helper base exponent limit soFar =
        let next = base ^ exponent in
          if next > limit then
            Ok soFar
          else
            helper base (exponent + 1) limit (next :: soFar)
    in
      case helper base 0 limit [] of
        Ok powerList -> Ok <| List.reverse powerList
        Err message -> Err message

This passes all the tests but I am wondering two things:

  1. Is consing (::) and then reversing at the end the right way to do this or is there a better way?
  2. Is there something amazing in Elm's List module that I missed that I should be using here?
  3. At the very end, when I wanted to reverse, was it necessary to do that matching? It seems unnecessarily verbose because I had to pass through the whole Err part. Since I only wanted to reverse a list in the Ok case and leave the Err part unchanged, was there a better way to write this?
\$\endgroup\$
2
\$\begingroup\$

Why don't you just use the exponentiation (^) operator? Using that you can omit the recursion at all:

powers : Int -> Int -> Result String (List Int)
powers base limit =
    if base < 0 then
        Err "negative base"
    else
        let size = floor (logBase (toFloat base) (toFloat limit))
        in Ok (List.map (\i -> base ^ i) (List.range 0 size))

There are some functions I used here:

  • logBase calculates the logarithm of a number with a given base. This can help to calculate the size of the returned list.
  • List.range : Int -> Int -> List Int generates an Int list where every element increasing by one.
\$\endgroup\$
  • 1
    \$\begingroup\$ Ah beautiful. I was hoping to do it with List.map but did not think of List.range! \$\endgroup\$ – Ray Toal Nov 6 '17 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.