LINUX.ORG.RU

Haskell и Foldable

 ,


1

4

Всем привет.

Познаю хаскель, наткнулся на проблему.

Есть простое дерево с лесом:

data RoseTree a = RoseEmpty | RoseTree a [RoseTree a]                                  
                    deriving (Show,Eq)

Пытаюсь реализовать для него интерфейс тайпкласса Foldable:

instance Foldable RoseTree where                                                       
    foldr _ acc RoseEmpty       = acc                                           
    foldr f acc (RoseTree x []) = f x acc                                       
    foldr f acc (RoseTree x ts) = let mapped    = map (foldr f acc) ts          
                                      folded    = foldr f acc mapped            
                                  in f x folded

Идея простая: чтобы свернуть список поддеревьев, применяю частично примененный (foldr f acc) к списку, получаю вместо списка поддеревьев (RoseTree a) список значений (a), потом сворачиваю список значений и применяю функцию f к значению ноды из паттерна и свернутому значению поддеревьев.

Но получаю ошибку в ghci:

error:
    • Couldn't match type ‘b’ with ‘a’
      ‘b’ is a rigid type variable bound by
        the type signature for:
          foldr :: forall a b. (a -> b -> b) -> b -> RoseTree a -> b
        at lecture11.hs:131:5
      ‘a’ is a rigid type variable bound by
        the type signature for:
          foldr :: forall a b. (a -> b -> b) -> b -> RoseTree a -> b
        at lecture11.hs:131:5
      Expected type: [a]
        Actual type: [b]
    • In the third argument of ‘foldr’, namely ‘mapped’
      In the expression: foldr f acc mapped
      In an equation for ‘folded’: folded = foldr f acc mapped
    • Relevant bindings include
        folded :: b (bound at lecture11.hs:134:39)
        mapped :: [b] (bound at lecture11.hs:133:39)
        ts :: [RoseTree a] (bound at lecture11.hs:133:29)
        x :: a (bound at lecture11.hs:133:27)
        acc :: b (bound at lecture11.hs:133:13)
        f :: a -> b -> b (bound at lecture11.hs:133:11)

Насколько я понимаю, ругань на то, что частично примененный (foldr f acc) получает на вход список не того типа. Но не могу понять почему, ведь этот foldr есть мой рекурсивный вызов и по идее он должен выглядеть так:

map (foldr f acc) ts

или для примера

map (foldr (+) 0) [RoseTree 1 [], RoseTree 2 [], RoseTree 3 []]

т.е.

[foldr (+) 0 (RoseTree 1 []), foldr (+) 0 (RoseTree 2 []), foldr (+) 0 (RoseTree 3 [])]

и по одной из моих реализаций Foldable RoseTree, где

foldr f acc (RoseTree x []) = f x acc

, получаем [1, 2, 3], что подтверждается пошаговым биндингом этого кода в ghci, но вот целиком ghci мой Foldable не проглатывает.

В чем проблема, парни?

Ответ на: комментарий от Crocodoom

А вот инстанс Foldable для обхода в ширину реализовать через cata algebra никак не получается

А если

instance Foldable BreadthTree where
    foldMap f (Breadth t) = foldMap f $ concat $ cata algebra t where
        algebra :: TreeF a [[a]] -> [[a]]
        algebra (Tree a rs) = [[a]] ++ breadth rs where
        breadth :: [[[a]]] -> [[a]]
        breadth rs =
          let l = [concat $ map head1 rs] in
          case l of
            [[]] -> []
            _ -> l ++ breadth (map tail rs) where
        head1 (x:xs) = x
        head1 _ = []
?

monk ★★★★★ ()
Ответ на: комментарий от monk

Так нельзя. Катаморфизм — это гомоморфизм между начальной F-алгеброй (A, in) и некоторой другой F-алгеброй (X, f). Чтобы назвать некоторую функцию h катаморфизмом, мы должны предъявить соответствующую пятёрку F, A, in, X, f. И из этой пятерки h определяется однозначно.

Для типов данных type t = Fix f, представленных через Fix, он же Mu, он же type-level fixpoint combinator, тип функции cata выписывается как:

cata :: Functor f => (f r -> r) -> (Fix f -> r)

Если вы говорите, что некоторая функция h = foldMap f :: Tree a -> m является катаморфизмом, то тут же связываете себя типом

cata :: (TreeF a m -> m) -> (Tree a -> m)

Но вместо этого вы взяли

cata :: (TreeF a [[a]] -> [[a]]) -> (Tree a -> [[a]])

Поэтому всё, что вы можете называть катаморфизмом для различных алгебр, это соответствующие функции cata algebra :: Tree a -> [[a]], а этот тип не совпадает с Tree a -> m.

Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

Но это не значит, что поиск в ширину уж совсем какой-то плохой с точки зрения теории категорий :) Поиск в ширину (как и поиск в глубину) является, например, анаморфизмом. Анаморфизм — это дуальное понятие к катаморфизму. Если катаморфизм — это обобщение свёртки списков, то анаморфизм — обобщение развёртки (unfoldr) списков.

Впрочем, здесь можно не извращаться с Fix и Data.Fix.ana, а просто воспользоваться стандартным unfoldr. Причём DFS от BFS будет отличаться лишь одним штришком.

import Data.Tree                                                                
import Data.List                                                                
                                                                                
t = Node 1 [Node 2 [Node 3  [Node 4  [], Node 5  []],                           
                    Node 6  [Node 7  [], Node 8  []]],                          
            Node 9 [Node 10 [Node 11 [], Node 12 []],                           
                    Node 13 [Node 14 [], Node 15 []]]]                          
                                                                                
-- bfs t == [1,2,9,3,6,10,13,4,5,7,8,11,12,14,15]                               
bfs :: Tree a -> [a]                                                            
bfs (Node a ts) = a : unfoldr next ts where                                     
    next [] = Nothing                                                           
    next ((Node a ts):ts') = Just (a, ts' ++ ts)                                
                                                                                
-- dfs t == [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]                               
dfs :: Tree a -> [a]                                                            
dfs (Node a ts) = a : unfoldr next ts where                                     
    next [] = Nothing                                                           
    next ((Node a ts):ts') = Just (a, ts ++ ts')

Красота, да и только.

Crocodoom ★★ ()
Ответ на: комментарий от Crocodoom

Красота, да и только.

Круто! Благодарю!

Кстати, случайно не знаешь, есть ли в Haskell чистые версии хэшей и массивов? В смысле со сложностью изменения O(n), так как полное копирование, но со сложностью чтения O(1).

А то на stackoverflow предлагают делать

lookup :: (Eq k, Hashable k) => HT k v -> k -> Maybe v
lookup (HT h) k = unsafePerformIO $ H.lookup h k

Не хочу unsafePerformIO

monk ★★★★★ ()
Последнее исправление: monk (всего исправлений: 1)