Найти список из списка в Haskell

Question

Я думаю, что мой код, чтобы найти среднее из списка (целых чисел), работает нормально, но имеет проблему. Это мой код

listlen xs = if null xs 
      then 0 
      else 1 + (listlen (tail xs)) 

sumx xs = if null xs 
     then 0 
     else (head xs) + sumx (tail xs) 

mean xs = if null xs 
      then 0 
      else (fromIntegral (sumx xs))/(fromIntegral (listlen xs)) 

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

Я хотел бы знать более эффективный способ сделать это (используя элементарную Haskell - это аа вопрос от Real World Haskell главы 3.)

Answer 1

что @simonzack намекает на то, что вы должны написать listlen и sumx, как складки.

Здесь listlen написано как раз:

listlen :: [a] -> Int 
listlen xs = go 0 xs     -- 0 = initial value of accumulator 
    where go s [] = s     -- return accumulator 
     go s (a:as) = go (s+1) as -- compute the next value of the accumulator 
            -- and recurse 

Здесь s является аккумулятором, который передается от одной итерации функции хелперного go к следующей итерации. Это значение возвращается, когда конец списка достигнут.

sumx Запись как раз будет выглядеть следующим образом:

sumx :: [a] -> Int 
sumx xs = go 0 xs 
    where go s [] = s 
     go s (a:as) = go ... as  -- flll in the blank ... 

Дело в том, что при наличии двух сгибы вы всегда можете комбинировать их, чтобы они вычисляются вместе.

lenAndSum :: [a] -> (Int,Int) 
lenAndSum xs = go (0,0) xs    -- (0,0) = initial values of both accumulators 
    where go (s1,s2) [] = (s1,s2)  -- return both accumulators at the end 
     go (s1,s2) (a:as) = go ... as -- left as an exercise 

Теперь вы вычислили обе функции с одним обходным списком списка.

Answer 2

Определить вспомогательную функцию, которая идет только через один раз:

lengthAndSum xs = if null xs 
        then (0,0) 
        else let (a,b) = lengthAndSum(tail xs) in (a + 1, b + head xs) 

mean xs = let (a, b) = lengthAndSum xs in (fromIntegral b/fromIntegral a) 

Answer 3

Мне нравятся другие ответы здесь. Но мне не нравится, что они пишут рекурсию вручную. Есть много способов сделать это, но один из них - повторное использование оборудования Monoid, которое у нас есть.

Data.Monoid Data.Foldable> foldMap (\x -> (Sum x, Sum 1)) [15, 17, 19] 
(Sum {getSum = 51}, Sum {getSum = 3}) 

Первая часть пары является суммой, а вторая часть является длина (вычисляется как сумма как можно большего числа 1 с, как есть элементы в списке). Это довольно общий шаблон: многие статистические данные могут быть отлиты как моноиды; и пары моноидов являются моноидами; поэтому вы можете вычислить столько статистики о какой-либо вещи, сколько хотите за один проход, используя foldMap. Вы можете увидеть еще один пример этого шаблона в this question, в котором я получил эту идею.

Answer 4

Теперь есть идея: функция, которая берет кучу моноидов и применяет каждый к списку, в одно и то же время. Но это может произойти позже!

Я думаю, что вам нужно, это раз, и кортеж для хорошей скорости:

avg :: (Fractional a) => [a] -> a 
avg [] = error "Cannot take average of empty list" 
avg nums = let (sum,count) = foldr (\e (s,c) -> (s+e,c+1)) (0,0) nums 
      in sum/count 

Я попытался это, и это прилично быстрый в GHCi, хотя это не может быть лучшим ,Я придумал рекурсивный метод, тоже, хотя это требует вспомогательной функции:

avg :: (Fractional a) => [a] -> a 
avg []  = error "Cannot take average of empty list" 
avg nums = let (sum, count) = go nums 
      in sum/count 
    where go [] = (0,0) 
      go (x:xs) = let (sum',count') = go xs 
         in (sum' + x, count' + 1) 

Тогда опять же, это действительно медленно. Болезненно медленно.

Рассматривая ваше решение, все в порядке, но это не идиоматический Haskell. if Операторы в функциях, как правило, работают лучше по сравнению с шаблоном, особенно если экземпляр класса Eq не определен для такого-то типа данных. Кроме того, как показано в моем примере, складки красивые! Они позволяют Haskell лениться и, следовательно, быстрее. Это мои отзывы и мое предложение в ответ на ваш вопрос.