Alternative way to write a Haskell function of single input and output of this kind-CodePudding

Good morning everyone!

I'm using the following function as a fitting example of a function that needs to have a simple input and output. In this case it's a function that converts a number from decimal to binary form, as a list of digits no less, just because it is convenient later on.

I chose to write it like this, because even though a number goes in and a list comes out, another structure is needed as an intermediate step, that will hold the digits found so far and hold the quotient of the division, as input for the next step of the loop. I will clean up the necessary mess before outputing anything, though, by selecting the part of the structure that I'm interested in, in this case the second one , and not counters or other stuff, that I'm done with. (As I mentioned this is an example only, and it's not unusual in other cases to initialize the until loop with a triplet like (a,b,c), only to pick one of them at the end, as I see fit, with the help of additional function, like pickXof3.)

So there,

dec2Bin :: Int -> [Int]
dec2Bin num = snd $ until 
                       (\(n,l) -> n <=0) -- test
                       (\(n,l) -> (fst $ division n, (snd $ division n):l)) -- main function
                       (num,[]) -- initialization
   where division a = divMod a 2

I find it very convenient that Haskell, although lacking traditional for/while loops has a function like until, which reminds me very much of Mathematica's NextWhile, that I'm familiar with.

In the past I would write sth even uglier, like two functions, a "helper" one and a "main" one, like so

dec2BinHelper :: (Int,[Int]) -> (Int,[Int])
dec2BinHelper (n,l)
   | n <= 0 = (n,l)
   | otherwise = dec2BinHelper (fst $ division n, (snd $ division n):l)
   where division a = divMod a 2

-- a function with the sole purpose to act as a front-end to the helper function, initializing its call parameters and picking up its output
dec2Bin :: Int -> [Int]
dec2Bin n = snd $ dec2BinHelper (n,[])

which I think is unnecessarily bloated.

Still, while the use of until allows me to define just one function, I get the feeling that it could be done even simpler/easier to read, perhaps in a way more fitting to functional programming. Is that so? How would you write such a function differently, while keeping the input and output at the absolutely essential values?

CodePudding user response：

I strongly prefer your second solution. I'd start a clean-up with two things: use pattern matching, and use where to hide your helper functions. So:

dec2Bin :: Int -> [Int]
dec2Bin n = snd $ dec2BinHelper (n, []) where
    dec2BinHelper (n, l)
        | n <= 0 = (n, l)
        | otherwise = dec2BinHelper (d, m:l)
        where (d, m) = divMod n 2

Now, in the base case, you return a tuple; but then immediately call snd on it. Why not fuse the two?

dec2Bin :: Int -> [Int]
dec2Bin n = dec2BinHelper (n, []) where
    dec2BinHelper (n, l)
        | n <= 0 = l
        | otherwise = dec2BinHelper (d, m:l)
        where (d, m) = divMod n 2

There's no obvious reason why you should pass these arguments in a tuple, rather than as separate arguments, which is more idiomatic and saves some allocation/deallocation noise besides.

dec2Bin :: Int -> [Int]
dec2Bin n = dec2BinHelper n [] where
    dec2BinHelper n l
        | n <= 0 = l
        | otherwise = dec2BinHelper d (m:l)
        where (d, m) = divMod n 2

You can swap the arguments to dec2BinHelper and eta-reduce; that way, you will not be shadowing the definition of n.

dec2Bin :: Int -> [Int]
dec2Bin = dec2BinHelper [] where
    dec2BinHelper l n
        | n <= 0 = l
        | otherwise = dec2BinHelper (m:l) d
        where (d, m) = divMod n 2

Since you know that n > 0 in the recursive call, you can use the slightly faster quotRem in place of divMod. You could also consider using bitwise operations like (.&. 1) and shiftR 1; they may be even better, but you should benchmark to know for sure.

dec2Bin :: Int -> [Int]
dec2Bin = dec2BinHelper [] where
    dec2BinHelper l n
        | n <= 0 = l
        | otherwise = dec2BinHelper (r:l) q
        where (q, r) = quotRem n 2

When you don't have a descriptive name for your helper function, it's traditional to name it go or loop.

dec2Bin :: Int -> [Int]
dec2Bin = go [] where
    go l n
        | n <= 0 = l
        | otherwise = go (r:l) q
        where (q, r) = quotRem n 2

At this point, the two sides of the conditional are short enough that I'd be tempted to put them on their own line, though this is something of an aesthetic choice.

dec2Bin :: Int -> [Int]
dec2Bin = go [] where
    go l n = if n <= 0 then l else go (r:l) q
        where (q, r) = quotRem n 2

Finally, a comment on the name: the input isn't really in decimal in any meaningful sense. (Indeed, it's much more physically accurate to think of the input as already being in binary!) Perhaps int2Bin or something like that would be more accurate. Or let the type speak for itself, and just call it toBin.

toBin :: Int -> [Int]
toBin = go [] where
    go l n = if n <= 0 then l else go (r:l) q
        where (q, r) = quotRem n 2

At this point I'd consider this code quite idiomatic.