#function #haskell #higher-order-functions
#функция #haskell #функции более высокого порядка
Вопрос:
Я хочу написать функцию f , которая преобразует двоичный список в целое число, например:
f :: [Integer] -> Integer
f [] = 0
f list = (last list) * 2^(length list -1) f (init list)
Например, в f [1,1,1,1,0,0,1,0] = 79 первый элемент списка представляет 2 ^ 0, а последний элемент списка представляет 2 ^ 7.
Могу ли я написать эту функцию с помощью функций более высокого порядка вместо явной рекурсии?
Комментарии:
1. Да, вы можете сделать это с
foldlпомощью .2. Вот что я подумал, но как я могу обработать (список длин -1) в foldl?
3. Забудьте о возведении в степень и
length. Подумайтеabcd = 1*d 2*c 2*2*b 2*2*2*a = 1*d 2*(c 2*(b 2*a))).4. @Sambud_Ger: вам не нужна длина, если вы каждый раз умножаете на два и добавляете значение, в конечном итоге вы получаете
2^n.5. molbdnilo ссылается на метод Хорнера .
Ответ №1:
Похоже, что порядок вашего списка неудачен для foldl, но вы можете передать показатель степени следующим образом:
intvalueOfList = fst . foldl f (0,1)
where f (acc,exp) e = (acc e*exp, exp*2)
Ответ №2:
Вы можете использовать foldr :: Foldable f => (a -> b -> b) -> b -> f a -> b which использует функцию «сворачивания», которая принимает элемент и накопитель. Концептуально накопитель выполняется справа налево по списку. Таким образом, вы можете каждый раз увеличивать накопитель, а затем добавлять значение элемента:
f :: (Foldable f, Num a) => f a -> a
f = foldr g 0
where g x acc = … где вам все еще нужно заполнить g .