1

I am learning Haskell, and I am solving problem 30 on project Euler.

digits n = if n<10 then [n] else (digits (quot n 10)) ++ [(mod n 10)]
isP30 n = (sum $ map (^5) $ digits n) == n
sum $ filter isP30 [10^5..10^6-1]

Is there a more readable way to implement the digits function ?

Uri Goren
  • 13,386
  • 6
  • 58
  • 110
  • 1
    How about using an [unfold](http://hackage.haskell.org/package/base-4.9.0.0/docs/Data-List.html#v:unfoldr)? – Benjamin Hodgson Nov 03 '16 at 13:10
  • @BenjaminHodgson , could you please elaborate ? – Uri Goren Nov 03 '16 at 13:23
  • 1
    `unfoldr` generalizes a loop which produces a list element at every step. All you have to do is defining a function which, given the current loop "state", decides whether to stop producing list values (`Nothing`) or produce a value (`x`) and loop again with a new state (`s`) (done with `Just (x,s)`. For instance `unfoldr (\n -> if n == 10 then Nothing else Just(n,n+1)) 0` will produce `[0..9]`. You can use this to produce your digits backwards, and `reverse` them at the end. – chi Nov 03 '16 at 13:47
  • 1
    Also keep in mind that appending as in `list ++ [x]` is inefficient, unlike prepending, since it needs to copy the whole list every time. It's much better to prepend elements and `reverse` the final list, so that only one copy is done. – chi Nov 03 '16 at 13:51
  • @chi re: "copy ... every time": [not exactly](https://stackoverflow.com/questions/14938584/haskell-foldl-poor-performance-with/14942678#14942678), i.e. nothing is copied. – Will Ness Nov 03 '16 at 18:27

3 Answers3

3

What about:

digits n = fmap digitToInt $ show n

I forgot to mention that you need to import digitToInt from Data.Char first, as in @bheklilr's answer.

bwroga
  • 5,379
  • 2
  • 23
  • 25
2

Using @BenjaminHodgson's suggestion, you can write an unfold as

import Data.Tuple (swap)
import Data.List (unfoldr)

digits = unfoldr go
    where go 0 = Nothing
          go n = Just (swap $ n `divMod` 10)

However, due to how unfoldr works you will get the digits in reverse order here. Another solution is to ditch this entirely and go with

import Data.Char (digitToInt)

digits = map digitToInt . show

My timings found it to be faster and use about 25% of the memory in an unoptimized GHCi session, it also doesn't reverse the order of the digits.

bheklilr
  • 53,530
  • 6
  • 107
  • 163
2

First of all it is always more readable to write code with guards, instead of if-then-else. All the extraneous parens are also distracting.

The standard transformation for the inefficient appending-at-end functions, like your

digits n | n < 10    = [n] 
         | otherwise = digits (quot n 10) ++ [mod n 10]

is to introduce an additional argument, where calling the old digits n ++ xs is the same as calling the new go n xs:

digits n = go n []   -- digits_old n ++ [] == go n []
   where
   go n next | n < 10    = n : next
             | otherwise = go (quot n 10) (mod n 10 : next)

--                            [a,b,c,...,x,y]         [z]
--                            [a,b,c,...,x]         [y,z]

Thus the digits being produced in the reversed order go one by one into the result list being built bottom-to-the-top in an accumulator parameter, resulting in the list created in the correct order.

Will Ness
  • 70,110
  • 9
  • 98
  • 181
  • I was going to just say it's not *always* more readable with guards, but that's mostly because `MultiWayIf` wasn't originally part of Haskell. If it had been, we'd probably write something like `if | c -> te | else tf`, or possibly even `if | c -> te | else -> tf`. – dfeuer Apr 14 '22 at 14:59
  • @dfeuer the original McCarthy's syntax was quite nice. `{ a -> b ; c -> d ; e }`. – Will Ness Apr 14 '22 at 18:06
  • Also, the contention was that guards are always more readable than the literal `if-then-else`, really. :) – Will Ness Apr 18 '22 at 10:22