haskell - 将位置、值元组列表转换为单个列表
问题描述
我正在编写一些代码来处理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
推荐阅读
- javascript - React how to highlight multiple components by using 1 ref
- c# - dotnetzip 创建空的损坏文件
- jestjs - Jest 的 --findRelatedTests 没有注意到 JSON 文件
- webhooks - Microsoft Teams,传入 Webhook 连接器,配置保存 403 错误
- python - 如果键相同,则相交两个字典python以获取两个字典的共同元素的有效方法
- angular-material - 输入在 Angular Material 扩展面板中不起作用。无法添加空间
- java - on Activity 创建恢复微调器对象
- java - 运行 EMR 时出现“错误:无法找到或加载主类”?
- python - 为什么 lambda 无法识别实例的属性?
- javascript - 尝试与 css display: inline-block 并排显示缩略图 img