Обобщение суммы списков Haskell

Произвольно вложенный список представляет собой дерево.

data Tree a = Empty | Leaf a | Branch (Tree a) (Tree a)

Итак, ваша функция sumList2 в Python станет функцией sumTree в Haskell.

sumTree :: Tree Int -> Int
sumTree Empty = 0
sumTree (Leaf n) = n
sumTree (Branch l r) = sumTree l + sumTree r

Чтобы понять, почему произвольно вложенный список представляет собой дерево, давайте посмотрим на некоторые визуализации. Рассмотрим следующий список на Python.

primes = [2, 3, 5, 7]

В Haskell мы можем визуализировать этот список следующим образом.

 (:)
 / \
2  (:)
   / \
  3  (:)
     / \
    5  (:)
       / \
      7   []

Внутренние узлы — это конструкторы cons, т. е. (:). Левая сторона минусов — это голова, а правая — хвост. Левые дочерние узлы минусов являются значениями списка. Самый правый узел — это пустой список.

Как видите, список — это просто очень несбалансированное дерево.

Теперь рассмотрим следующий произвольно вложенный список в Python.

primes = [[2, [[], 3]], [5, [7, []]]]

В Haskell мы можем визуализировать этот список следующим образом.

     (:)
     / \
    /   \
   /     \
 (:)     (:)
 / \     / \
2  (:)  5  (:)
   / \     / \
 []   3   7   []

Как видите, оно похоже на дерево. Листья либо пусты, либо содержат какие-то данные. Списки в Haskell не могут представлять собой древовидную структуру. Следовательно, мы создаем тип данных Tree. Следовательно, давайте обновим визуализацию.

               Branch
                / \
               /   \
              /     \
             /       \
            /         \
           /           \
     Branch             Branch
      / \                / \
Leaf 2   Branch    Leaf 5   Branch
          / \                / \
     Empty   Leaf 3    Leaf 7   Empty

И именно поэтому произвольно вложенный список в Python становится деревом в Haskell.

Int, [Int], [[Int]] и т. д. — это разные типы, и тип функции выбирается в момент ее вызова. Если мы ожидаем, что наша функция вернет Int, и у нас есть два предложения

sumList (x:xs) = {- does not matter what goes here -}
sumList x = x

тогда мы гарантируем, что независимо от того, какой тип входных данных мы выберем, мы получим ошибку типа. Если мы выберем Int, то первое предложение будет ошибкой, поскольку x:xs может соответствовать только спискам; если мы выберем любой тип списка, то второе предложение будет ошибкой, поскольку оно не возвращает Int.

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

class Sums a where sums :: a -> Int
instance Sums Int where sums x = x
instance Sums a => Sums [a] where
    sums [] = 0
    sums (x:xs) = sums x + sums xs

Теперь, когда мы вызываем sums, мы никогда не вызываем функцию, имеющую оба предложения; вместо этого мы просим компилятор вызвать ту или иную из этих функций в зависимости от того, какой конкретный тип был выбран. Линия

    sums (x:xs) = sums x + sums xs

может выглядеть подозрительно, поскольку мы знаем, что x и xs имеют разные типы. Но нас спасает тот факт, что они вызывают не одну и ту же sums функцию! Опять же, тип функции выбирается в момент ее вызова, и здесь есть два разных вызова, которые могут выбирать два разных типа, после чего компилятор выберет разные функции для вызова.

Другой вариант, который у нас есть, — создать новый тип. Проблема с тем, что Int, [Int], [[Int]] и т. д. являются разными типами, заключается в том, что это означает, что мы должны статически знать, насколько глубоко вложен список. Если мы этого не знаем, то нам нужен тип, который может выразить тот факт, что его глубина вложенности известна только динамически, и который отслеживает данные, которые ему необходимо знать, чтобы определить, насколько глубока эта вложенность. Один из способов сделать это:

data DynList a = NotNested a | Nested [DynList a]

sumDynList :: DynList Int -> Int
sumDynList (NotNested x) = x
sumDynList (Nested []) = 0
sumDynList (Nested (x:xs)) = sumDynList x + sumDynList (Nested xs)

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

sumDynList (NotNested x) = x
sumDynList (Nested xs) = sum (map sumDynList xs)

Этот конкретный тип допускает различное количество вложений в разных точках структуры данных. Если вместо этого предполагается, что существует одна глубина вложенности и все элементы списка имеют одинаковую глубину, тогда нам нужен немного более продвинутый метод.

data SharedDepthList a = Depth0 a | Deeper (SharedDepthList [a])

sumSharedDepthList :: SharedDepthList Int -> Int
sumSharedDepthList = go id where
    go :: (a -> Int) -> SharedDepthList a -> Int
    go f (Depth0 x) = f x
    go f (Deeper xs) = go (sum . map f) xs

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

Обратите внимание, что встроенная библиотечная функция sum в Haskell полиморфна:

$ ghci
GHCi, version 9.4.5: https://www.haskell.org/ghc/  :? for help
ghci> 
ghci> :type  sum
sum :: (Foldable t, Num a) => t a -> a
ghci> 

Нам нужно найти трансформатор такого типа, который:

1. может представлять собой «обобщенные списки»
2. есть экземпляр Foldable.

К счастью, библиотека Haskell предоставляет такую ​​вещь под видом свободных монад.

По сути, у нас есть следующее определение типа:

data Free ft a = Pure a |  Impure (ft (Free ft a))

что, конечно, очень похоже на то, что дано в превосходном ответе Дэниела. Оказывается, если ft — функтор, то Free ft — монада, известная как «свободная» монада.

Например, правильное отображение [42,[5,10]] в таком контексте:

Impure [ Pure 42, Impure [ Pure 5, Pure 10 ] ]

Давайте попробуем использовать [] в качестве функтора:

ghci> 
ghci> import Control.Monad.Free
ghci> type GL = Free []
ghci> 
ghci> xss = Impure [ Pure 42, Impure [ Pure 5, Pure 10 ] ]  ::  GL Int
ghci> 
ghci> :instances GL
...
instance [safe] Foldable (Free [])
  -- Defined in ‘Control.Monad.Free’
...
ghci> 
ghci> :type xss
xss :: GL Int
ghci> 

Таким образом, библиотека предоставляет нам экземпляр Foldable, так что мы почти закончили.

ghci> 
ghci> foldl (+) 0 xss
57
ghci> sum xss
57
ghci> 

Вуаля!