Преобразование в римские цифры


Как упражнение в "Хаскелл: ремесло функциональное программирование", я создал некоторый код, чтобы преобразовать целое число в римские цифры.

Это первая версия и я думаю, что я, наверное, не делать это в "Хаскелл сторону", так как мой фон в императивном программировании.

Любые советы о том, как улучшить это? Иногда мне кажется, что я упускаю очевидный способ сделать это в одной функции.

convMap = [(1000,"M"), (900,"CM"), (500,"D"), (400,"CD"), (100,"C"),
           (90,"XC"), (50,"L"), (40,"XL"), (10,"X"), (9,"IX"), (5,"V"),
           (4,"IV"), (1,"I")]

toRoman :: Integer -> String
toRoman x 
  | x == 0 = "N"
  | otherwise = (snd . numToSubtract $ x) ++ toRoman'(nextNum)
      where nextNum = x - (fst. numToSubtract $ x)

-- Auxiliary function just so we treat 0 differently
-- (avoids 3 == "IIIN" if not used)
toRoman' :: Integer -> String
toRoman' x 
  | x == 0 = ""
  | x > 0 = (snd . numToSubtract $ x) ++ toRoman'(nextNum)
      where nextNum = x - (fst. numToSubtract $ x)

-- Returns which item in the convMap should be subtracted
numToSubtract :: Integer -> (Integer, String)
numToSubtract x = head (filter (lessThan x) convMap)

-- Filter function to work on the tuples in convMap
lessThan :: Integer -> (Integer, String) -> Bool
lessThan n (a, b)
  | a <= n = True
  | otherwise = False


2148
14
задан 24 октября 2011 в 01:10 Источник Поделиться
Комментарии
3 ответа

Переключатели нормальные значения:

lessThan n (a, b)
| a <= n = True
| otherwise = False

Просто написать:

lessThan n (a, _) = a <= n

Использовать сопоставление с образцом:

toRoman' :: Integer -> String
toRoman' x
| x == 0 = ""
| x > 0 = (snd . numToSubtract $ x) ++ toRoman'(nextNum)
where nextNum = x - (fst. numToSubtract $ x)

Если вы хотите взять ФСТ и СНД того же кортежа, думать о шаблону.
Незначительный момент: в скобках мнению'(nextNum) являются избыточными, просто напишите мнению' nextNum.

toRoman' :: Integer -> String
toRoman' x
| x == 0 = ""
| x > 0 = b ++ toRoman' (x - a)
where (a, b) = numToSubtract x

Удалить дублирования:

мнению и мнению' содержит дублировать код. В то мнению используется только для лечения специально 0, поэтому может быть изменен:

toRoman :: Integer -> String
toRoman 0 = "N"
toRoman x = toRoman' x

Переместить или удалить служебные функции:

меньше, чем и numToSubtract используются только один раз и, кажется, не быть полезным, может быть, рядный них:

toRoman' :: Integer -> String
toRoman' x
| x == 0 = ""
| x > 0 = b ++ toRoman' (x - a)
where (a, b) = head $ filter (\(a,_) -> a <= x) convMap

Как Дэн Бертон сказал, Вы можете написать также:

      where (a, b) = head $ filter ((<= x) . fst) convMap

Окончательный код

convMap = [(1000,"M"), (900,"CM"), (500,"D"), (400,"CD"), (100,"C"),
(90,"XC"), (50,"L"), (40,"XL"), (10,"X"), (9,"IX"), (5,"V"),
(4,"IV"), (1,"I")]

-- Auxiliary function just so we treat 0 differently
-- (avoids 3 == "IIIN" if not used)
toRoman :: Integer -> String
toRoman 0 = "N"
toRoman x = toRoman' x

toRoman' :: Integer -> String
toRoman' x
| x == 0 = ""
| x > 0 = b ++ toRoman' (x - a)
where (a, b) = head $ filter ((<= x) . fst) convMap

Фолд

Если вы смотрите немного в код, получается у вас каждая запись из convMap только один раз. Сначала вам узнать, сколько метров вам необходимо. Потом см. Затем Ди. И так далее. Используя функцию "фильтр" всегда перезапускается поиск с начала. На самом деле, мнению может быть записан как раз!

import Data.List (genericReplicate)

convMap = [(1000,"M"), (900,"CM"), (500,"D"), (400,"CD"), (100,"C"),
(90,"XC"), (50,"L"), (40,"XL"), (10,"X"), (9,"IX"), (5,"V"),
(4,"IV"), (1,"I")]

toRoman :: Integer -> String
toRoman 0 = "N"
toRoman x | x > 0 = snd $ foldl f (x,[]) convMap
where f (n,s) (rn, rs) = (l, s ++ concat (genericReplicate k rs))
where (k,l) = divMod n rn

Схожу с ума с абстракциями

Эрик Хилтон хороший ответ дает решение с использованием unfoldr. Так что вы можете писать код, используя складываются и раскладываются, и эти два способа смотреть на это. Я считаю, что комбинации складываются и раскладываются называется "paramorphism" или "apomorphism" или что-то подобное...

13
ответ дан 24 октября 2011 в 01:10 Источник Поделиться

Попробуйте что-то вроде этого

import Data.List
import Data.Maybe

convMap = [(1000,"M"), (900,"CM"), (500,"D"), (400,"CD"), (100,"C"),
(90,"XC"), (50,"L"), (40,"XL"), (10,"X"), (9,"IX"), (5,"V"),
(4,"IV"), (1,"I")]

intToRoman :: Int -> String
intToRoman = concat . unfoldr findLeast
where findLeast n = case i of
Just (x,r) -> Just(r,n-x)
Nothing -> Nothing
where i = find (\(val,_) -> val <= n) convMap

Unfoldr-это функция, которая, к сожалению, недостаточно, но именно то, что вы хотите здесь. Он принимает начальное значение, тот, который вы пытаетесь конвертировать и строит список (римского части). Это может быть немного более многословным, чем это абсолютно необходимо, но я считаю, что это очень ясно.

Заметка о том, как unfoldr работы: вы передаете его начальное значение и функция. эта функция возвращает либо просто(А,Б) или ничего. В первом случае, добавляется к аккуму и Б используется в качестве следующего начального значения. Это будет продолжаться до тех пор, пока функция возвращает ничего. В этот момент unfoldr завершена.

10
ответ дан 24 октября 2011 в 02:10 Источник Поделиться

Вот мой взгляд на это. Я изменил алгоритм немного, так что это только через convMap раз.

toRoman 0 = "N"
toRoman x | x < 0 = error "toRoman: negative number"
toRoman x = loop x convMap
where loop 0 _ = ""
loop x cs@((a, b):cs') | x >= a = b ++ loop (x - a) cs
| otherwise = loop x cs'

Картина, возможно, немного коряво, но кроме этого я думаю, что это и читаемой и эффективной. Вы также можете написать его как раз,

toRoman x = snd $ foldl f (x, []) convMap
where f (x, s) (a, b) = let (q, r) = quotRem x a in (r, s ++ concat (replicate q b))

но это немного менее эффективным из-за квадратичной добавления. Списки разницу будет работать, но это будет только сделать его хуже.

7
ответ дан 24 октября 2011 в 03:10 Источник Поделиться