Applicative Functors: Rose Trees with an alternate behavior
The rose trees implemented in Data.Tree behave in the same way as the applicative style on lists (ie all possible combinations/permutations). I need a different behavior: one-to-one application. So, using the Data.Tree code, if I start with this tree: *Main Data.Traversable> putStrLn $ drawTree (fmap show temp2) 1 | +- 2 | `- 3 and then try this: *Main Data.Traversable> putStrLn $ drawTree (fmap show $ sequenceA [temp2,temp2]) [1,1] | +- [1,2] | +- [1,3] | +- [2,1] | | | +- [2,2] | | | `- [2,3] | `- [3,1] | +- [3,2] | `- [3,3] It gives all the combinations/permutations. I need this: *Main Data.Traversable> putStrLn $ drawTree (fmap show $ seqA [temp2,temp2]) [1,1] | +- [2,2] | `- [3,3] But then only way I could get that result was to (re-)write my own sequenceA function (called it seqA), which I suspect shouldn't be necessary. If I use the built-in sequenceA, I get (only) this: *Main Data.Traversable> putStrLn $ drawTree (fmap show $ sequenceA [temp2,temp2]) [1,1] Here's my code: data Tree a = Node {fromNode :: !a, fromNodeForest :: !(Forest a)} deriving (Show, Eq) type Forest a = [Tree a] zipWithForest = zipWith emptyForest = [] instance Functor Tree where fmap f (Node x subtrees) = Node (f x) (fmap (fmap f) subtrees) instance Applicative Tree where pure x = Node x emptyForest (<*>) (Node f tfs) (Node cargo subtrees) = Node (f cargo) (zipWithForest (<*>) tfs subtrees) seqA :: (Applicative f) => [f a] -> f [a] seqA (x:xs) = foldr (liftA2 (:)) (fmap (const []) x) (x:xs) I think I've got something wrong in how I've defined the Applicative Functor methods, and "cheating" by writing a custom sequenceA function to work around the deficiency. What is the proper fix? thanks again, travis
On Tue, Aug 10, 2010 at 12:49:51AM -0700, Travis Erdman wrote:
The rose trees implemented in Data.Tree behave in the same way as the applicative style on lists (ie all possible combinations/permutations). I need a different behavior: one-to-one application.
instance Applicative Tree where pure x = Node x emptyForest (<*>) (Node f tfs) (Node cargo subtrees) = Node (f cargo) (zipWithForest (<*>) tfs subtrees)
Right, your definition of 'pure' is wrong. For these sorts of 'zippy' Applicative instances, pure should create an infinite data structure containing nothing but the given data element. For example, take a look at the Applicative instance for ZipList: instance Applicative ZipList where pure x = ZipList (repeat x) ... Why is this? Note that since <*> matches up two structures pointwise, the shape of the result is necessarily the intersection of the shapes of the two inputs. In order for laws like pure id <*> v = v to be satisfied, pure must create a structure which is "as large as possible" so that v does not get truncated. This is what was happening in your example -- since your implementation of 'pure' just created a one-element tree, the result of your call to sequenceA was getting truncated to this shape. The correct implementation of pure looks like this: pure x = Node x (repeat (pure x)) (Hooray for lazy infinite data structures!) With this definition the standard sequenceA works just fine. -Brent
participants (2)
-
Brent Yorgey -
Travis Erdman