Блог

Я пишу некоторый код для работы с произвольными исходными числами в haskell. Они будут сохранены в виде списков целых чисел, представляющих цифры.

Мне почти удалось заставить это работать, но я столкнулся с проблемой преобразования списка кортежей [(a_1, b_1), …,(a_n, b_n)] в единый список, который определяется следующим образом:

для всех i, L(a_i) = b_i. если нет i такого, что a_i = k, a(k)=0

Другими словами, это список пар (позиция, значение) для значений в массиве. Если позиция не имеет соответствующего значения, ей следует присвоить значение ноль.

Я прочитал это (https://wiki.haskell.org/How_to_work_on_lists ) но я не думаю, что какой-либо из этих методов подходит для этой задачи.

 baseN :: Integer -> Integer -> [Integer]
baseN n b = convert_digits (baseN_digits n b)

chunk :: (Integer, Integer) -> [Integer]
chunk (e,m) = m : (take (fromIntegral e) (repeat 0))

-- This is broken because the exponents don't count for each other's zeroes
convert_digits :: [(Integer,Integer)] -> [Integer]
convert_digits ((e,m):rest) = m : (take (fromIntegral (e)) (repeat 0)) 
convert_digits []       = []

-- Converts n to base b array form, where a tuple represents (exponent,digit).
-- This works, except it ignores digits which are zero. thus, I converted it to return (exponent, digit) pairs.
baseN_digits :: Integer -> Integer -> [(Integer,Integer)]

baseN_digits n b | n <= 0 = [] -- we're done.
          | b <= 0 = [] -- garbage input. 
          | True   = (e,m) : (baseN_digits (n-((b^e)*m)) b)
                     where e = (greedy n b 0)      -- Exponent of highest digit
                           m = (get_coef n b e 1)  -- the highest digit

-- Returns the exponent of the highest digit.
greedy :: Integer -> Integer -> Integer -> Integer
greedy n b e | n-(b^e) <  0  = (e-1) -- We have overshot so decrement.
             | n-(b^e) == 0  = e     -- We nailed it. No need to decrement. 
             | n-(b^e) >  0  = (greedy n b (e 1)) -- Not there yet.

-- Finds the multiplicity of the highest digit
get_coef :: Integer -> Integer -> Integer -> Integer -> Integer
get_coef n b e m | n - ((b^e)*m) < 0  = (m-1) -- We overshot so decrement.
                 | n - ((b^e)*m) == 0 = m    -- Nailed it, no need to decrement.
                 | n - ((b^e)*m) > 0  = get_coef n b e (m 1) -- Not there yet.
  

Вы можете вызвать «baseN_digits n base», и это выдаст вам соответствующий массив кортежей, который необходимо преобразовать в правильный результат

Вот кое-что, что я собрал вместе.

  f = snd . foldr ((e,n) (i,l') -> ( e , (n : replicate (e-i-1) 0)    l')) (-1,[])
 f . map (fromIntegral *** fromIntegral) $ baseN_digits 50301020 10 = [5,0,3,0,1,0,2,0]
  

Я думаю, что понял ваши требования (?)

РЕДАКТИРОВАТЬ: Возможно, более естественно,

 f xs = foldr ((e,n) fl' i -> (replicate (i-e) 0)    (n : fl' (e-1))) (i -> replicate (i 1) 0) xs 0