Trouble translating a function

Learn
#1

Hello all! I am gaetgu, and I have been experimenting with haskell for the past week or so. I have previous experience (see: I made a couple of toy projects in) erlang, so I am not totally new to functional programming. I am currently working on translating an encoding system for a game called FreeRider from rust (or python as a reference), and I am having trouble with the main function.

This function (rust) encodes a 32bit integer into a sort of subset of Base32.

pub fn base32_encode(target: i32) -> String {
    let alphabet: Vec<char> = vec!['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a',
                                    'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l',
                                    'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v'];

    let mut number = target.abs();
    let mut final_data = String::new();
    let mut i: i32;
    while number != 0 {
        i = number % 32;
        number = (number - 1) / 32;
        final_data = format!("{}{}", alphabet[i as usize].to_string(), final_data);
    }
    if target < 0 {
        final_data = format!("{}{}", "-", final_data);
    }

    if final_data != "".to_string() {
        return final_data;
    } else {
        return alphabet[0 as usize].to_string();
    }
}

It is created in a very imperative style of coding, which I think is why I am having trouble translating it. Here is my current implementation in haskell:

alphabet :: [String]
alphabet = words "0 1 2 3 4 5 6 7 8 9 a b c d e f g h i j k l m n o p q r s t u v"

base32' :: Int -> String -> String
base32' x result
    | xa /= 0   = base32' ((xa - 1) `div` 32) (alphabet !! (xa `mod` 32) ++ result)
    | x < 0     = base32' xa "-" ++ result
    | otherwise = result
    where xa = abs x

The problem with this approach is that it does not encode negatives correctly. For example, given -40, the rust program will output “-18”, while the haskell equivalent will simply output “18”.

I know that at least one problem with this is that the x < 0 guard is after the xa /= 0 guard, but moving it up to a higher priority creates improperly negated numbers.

I have been trying to do this for a couple of hours now with multiple different function styles from imperative-styled to functional styled (such as the example above), and I am really stumped. If anyone is willing to just give me a different perspective rather than solving the problem for me, great! I am happy to hear just about anything that you can tell me.

Thanks alot!

#2

Separate the recursion into its own function. Apply the sign handling to the result of the recursive function.

1 Like
#3

This is how I would write it:

alphabet :: [Char]
alphabet = "0123456789abcdefghijklmnopqrstuv"

base32 :: Int -> String
base32 n = case compare n 0 of
  LT -> '-' : go (negate n) ""
  EQ -> "0"
  GT -> go n ""
  where
    go 0 res = res
    go n res = let (q,r) = n `quotRem` 32 in go q (alphabet !! r : res)
1 Like
#4

Aside from the algorithm, you can use Int32 from Data.Int to more accurately translate the Rust (and would behave the same).

A Data.Array or Data.Vector would give you the O(1) lookup that you’re getting with Rust’s vector type.

Also you’d ideally produce a Text from Data.Text which is, as of recently, also a vector of bytes in UTF-8, like Rust. String is just a linked list.

Picking the right types will lead to better performance characteristics. As for the algorithm, the practice you’re doing now is best. But you can look at common combinator like scan, fold, mapAccum, etc. which are present in Data.List, Data.Vector, and Data.Text and let you do more high level looping than doing recursion manually.

1 Like
#5

Thanks everyone for your help! I am currently using jaror’s solution as it works fine, but I also might implement some of the things mentioned by chrisdone.