Collecting values from Functors?
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor. For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values? #g ------------------- Graham Klyne <GK@NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
No, you need a fold to do that. -- Hal Daume III | hdaume@isi.edu "Arrest this man, he talks in maths." | www.isi.edu/~hdaume On Wed, 4 Jun 2003, Graham Klyne wrote:
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor.
For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values?
#g
------------------- Graham Klyne <GK@NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
On Wed, Jun 04, 2003 at 11:15:30AM -0700, Hal Daume III wrote:
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor.
For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values?
No, you need a fold to do that.
Or a variant of Functor constructor class that I have proposed some time ago on comp.lang.functional: class FunctorM t where fmapM :: Monad m => (a -> m b) -> (t a -> m (t b)) fmapM_ :: Monad m => (a -> m b) -> (t a -> m ()) fmapM_ f t = fmapM f t >> return () instance FunctorM [] where fmapM = mapM fmapM_ = mapM_ Best regards, Tom -- .signature: Too many levels of symbolic links
On Wed, Jun 04, 2003 at 08:38:29PM +0200, Tomasz Zielonka wrote:
On Wed, Jun 04, 2003 at 11:15:30AM -0700, Hal Daume III wrote:
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor.
For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values?
No, you need a fold to do that.
Or a variant of Functor constructor class that I have proposed some time ago on comp.lang.functional:
class FunctorM t where fmapM :: Monad m => (a -> m b) -> (t a -> m (t b)) fmapM_ :: Monad m => (a -> m b) -> (t a -> m ()) fmapM_ f t = fmapM f t >> return ()
instance FunctorM [] where fmapM = mapM fmapM_ = mapM_
I am sorry, I misunderstood the problem. Best regards, Tom -- .signature: Too many levels of symbolic links
Tomasz Zielonka writes: | On Wed, Jun 04, 2003 at 08:38:29PM +0200, Tomasz Zielonka wrote: : | > Or a variant of Functor constructor class that I have proposed some time | > ago on comp.lang.functional: | > | > class FunctorM t where | > fmapM :: Monad m => (a -> m b) -> (t a -> m (t b)) | > fmapM_ :: Monad m => (a -> m b) -> (t a -> m ()) | > fmapM_ f t = fmapM f t >> return () | > | > instance FunctorM [] where | > fmapM = mapM | > fmapM_ = mapM_ | | I am sorry, I misunderstood the problem. You're too modest. :-) There *is* a solution in that direction. Here's my version of fmapM, which was inspired by something in Tim Sheard's paper "Generic Unification via Two-Level Types and Parameterized Modules". import Control.Monad.State -- ------------------------------------------------------------ -- Functors through which monads may be lifted class Functor f => FunctorSeq f where fseq :: Monad m => f (m a) -> m (f a) instance FunctorSeq [] where fseq = sequence instance FunctorSeq Maybe where fseq Nothing = return Nothing fseq (Just mx) = do x <- mx; return (Just x) fmapM :: (Monad m, FunctorSeq f) => (a -> m b) -> f a -> m (f b) fmapM f xs = fseq (fmap f xs) fseq2list :: (FunctorSeq f) => f a -> [a] fseq2list fa = reverse (execState (fmapM (\a -> modify (a:)) fa) []) The question was "Suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values?" A: Yes, use something like fseq2list, provided that you first declare your tree type as an instance of something like FunctorM or FunctorSeq. Regards, Tom
In article <16094.24499.796592.366278@tux-17.corp.peace.com>, Tom Pledger <Tom.Pledger@peace.com> wrote:
Here's my version of fmapM, which was inspired by something in Tim Sheard's paper "Generic Unification via Two-Level Types and Parameterized Modules".
Gosh well I came across something very similar completely independently: class (Functor f) => ExtractableFunctor f where { fExtract :: forall g a. (FunctorApplyReturn g) => f (g a) -> g (f a); }; See <http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/hbase/Source/HBase/Catego ry/Functor.hs?rev=HEAD&content-type=text/vnd.viewcvs-markup> Btw FunctorApplyReturn is a larger class than Monad (should be a superclass IMO, but I'm not yet ready to define my own Monad class in HBase). In addition to fmap it has return' :: a -> f a fApply :: f (a -> b) -> (f a -> f b) ...from which one can derive liftF2. This makes fExtract more general and thus ExtractableFunctor more demanding; but I expect most of the types that are your FunctorSeq would also be ExtractableFunctor. So I've been using ExtractableFunctors in HScheme to handle recursive binding macro "letrec": data ZeroList a = MkZeroList; data NextList t a = MkNextList a (t a); These can be made ExtractableFunctors and allow lists where the type indicates the length, for instance: type List3 = NextList (NextList (NextList ZeroList)); I then use them to build up values of this type: data MutualBindings f a v = forall t. (ExtractableFunctor t) => MkMutualBindings (t (f a)) (forall r. f r -> f (t v -> r)); So here "t" is the list type. "f" is my clever SymbolExpression type, an instance of my equally clever FunctorLambda class. "a" is basically "m SchemeObject" where m is an appropriate Monad. "v" is a reference to a SchemeObject (simplifying here a certain amount). Think of the SymbolExpression type as encoding lambda-terms. You can do things such as find its free variables, etc. The first part of the MkMutualBindings is a list of expressions found in the "letrec" head. The second part is a function that abstracts based on the variables listed. For instance: (letrec ((a b) (b 3) (c a)) (+ c 1) ) Support for this kind of recursive binding is actually more than R5RS requires, but I thought it worth trying after I discovered how to write the fixed-point function mfix for my continuation-passing monad. The head of the letrec is parsed to make a MutualBindings. The first part of the MkMutualBindings would be essentially a List3 (above) of expressions representing "b", "3" and "a". The second part would be an "abstracting" function that turns a SymbolExpression of anything "r" to a SymbolExpression of a function that depended on a list of three references, by abstracting on the symbols "a", "b", and "c". You can kind of gloss it like this: MkMutualBindings bindValues abstracter; abstracter (f "(* a b c)") = f (\a b c -> "(* " ++ a ++ b ++ c ++ ")") Having constructed the MutualBindings, I then call foo (fExtract (fmap abstracter bindValues)) (abstracter body) "foo" is what I'm working on currently. I had an earlier version that only worked with the pure functional flavour of HScheme; I'm now generalising it with mfix. It's all in CVS... <http://sourceforge.net/cvs/?group_id=47823> -- Ashley Yakeley, Seattle WA
On Thu, Jun 05, 2003 at 09:08:03AM +1200, Tom Pledger wrote:
| I am sorry, I misunderstood the problem.
You're too modest. :-)
There *is* a solution in that direction.
Yes, I knew I could use a State monad or a Writer monad, but I thought that it would be an overkill. Fold is more appropriate here.
Here's my version of fmapM, which was inspired by something in Tim Sheard's paper "Generic Unification via Two-Level Types and Parameterized Modules".
import Control.Monad.State
-- ------------------------------------------------------------ -- Functors through which monads may be lifted
class Functor f => FunctorSeq f where fseq :: Monad m => f (m a) -> m (f a)
instance FunctorSeq [] where fseq = sequence
instance FunctorSeq Maybe where fseq Nothing = return Nothing fseq (Just mx) = do x <- mx; return (Just x)
fmapM :: (Monad m, FunctorSeq f) => (a -> m b) -> f a -> m (f b) fmapM f xs = fseq (fmap f xs)
fseq2list :: (FunctorSeq f) => f a -> [a] fseq2list fa = reverse (execState (fmapM (\a -> modify (a:)) fa) [])
I like this solution. The fseq function seems to be more general.
Regards, Tom
Regards, Tom :) -- .signature: Too many levels of symbolic links
At 20:40 04/06/03 +0200, Tomasz Zielonka wrote:
Or a variant of Functor constructor class that I have proposed some time ago on comp.lang.functional:
class FunctorM t where fmapM :: Monad m => (a -> m b) -> (t a -> m (t b)) fmapM_ :: Monad m => (a -> m b) -> (t a -> m ()) fmapM_ f t = fmapM f t >> return ()
instance FunctorM [] where fmapM = mapM fmapM_ = mapM_
I am sorry, I misunderstood the problem.
I think you responded usefully to the spirit of my question, if not the letter. I think I may be able to use these ideas. Your FunctorM class looks rather like the kind of idea I was wrestling with when I posted my question. If I define a monad to accumulate the desired result, and a monadic form of the transformation/collector function, then I think I can define and use fmapM to return a transformed expression (tree, or whatever) and pick the accumulated value from the monad. I'm trying to decide whether to try this (which has the advantage, AFAICT, of not using any language extension) or go for the a gmap based approach (which may, in the longer run, be more flexible). Mainly, I'm trying to figure which is easier in the near term. #g ------------------- Graham Klyne <GK@NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
Graham Klyne wrote:
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor.
For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values?
Rather than using fmap, why not use gmap in GHC. Using an appropriate generic traversal scheme, say listify, all the code you write is the following expression: listify (const True) mytree :: [Int] if you are looking for all the Ints in mytree = Fork (Leaf 42) (Fork (Leaf 88) (Leaf 37)) So this would give you [42,88,37]. (So you do not need to force your datatypes to become functors, neither do you write Functor instances.) I added this example to the boilerplate page. http://www.cs.vu.nl/boilerplate/ Ralf -- Ralf Laemmel VU & CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/
Rather than using fmap, why not use gmap in GHC. Using an appropriate generic traversal scheme, say listify, all the code you write is the following expression:
listify (const True) mytree :: [Int]
if you are looking for all the Ints in mytree = Fork (Leaf 42) (Fork (Leaf 88) (Leaf 37)) So this would give you [42,88,37].
What happens if the tree contains additional integers to record, say, balancing information. The information a functor provides is vital here. Take as the simplest example newtype Weighted a = WithWeight (Int, a) Without the functor definition there is no way to distinguish the two Ints in Weighted Int. Cheers, Ralf
Ralf Hinze wrote:
What happens if the tree contains additional integers to record, say, balancing information. The information a functor provides is vital here. Take as the simplest example
newtype Weighted a = WithWeight (Int, a)
Without the functor definition there is no way to distinguish the two Ints in Weighted Int.
You are right in that gmapping is not generally aware of term components that relate to the parameter of a parameterised datatype. This has to do with the restricted structural induction and with the bias towards nominal type case. One can still recover `type distinctions' by pattern matching however. I elaborated the example like this: http://www.cs.vu.nl/boilerplate/testsuite/foldTree.hs (More generally, it is certainly debatable if the gmap combinators are in place for more fancy datatypes, e.g., nested datatypes. I mean that the design and use of these datatypes is normally an ingenious process as opposed to boilerplate programming in the sense of AST or document traversal.) Ralf L. -- Ralf Laemmel VU & CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/
Ralf, Thanks. I've just retrieved and read "Scrap your boilerplate" [1]. I must say that, as a piece of exposition, I think this is an excellent paper (**). And technically, this is very much the sort of thing I was probing for. I think I'll focus some attention on gmapM and friends. (**) for feedback: as a relative newcomer to FP, the part I found most difficult to track was the section on gfoldl. I found that there was not quite enough motivation and coverage of its expected properties for me to get a real handle on. As it is, I'm left with a vague concept that it's a 1-level fold with some fancy type-wrapping. No doubt, in time, I'll gain a deeper appreciation. (My original question was intended to strip the question down to bare bones, separate from details of my desired application, but it may be worth mentioning some of those details. I have an expression (actually, a form of graph) that contains "constants" and "variables", and a variable substitution function. I wish to apply the substitution function across the graph (of itself a straightforward fmap), and also collect a list of variables in the graph for which no substitution was provided. All this in a way that separates details of the expression structure from details of the variable substitution.) #g -- [1] http://www.cs.vu.nl/boilerplate/#paper At 21:05 04/06/03 +0200, Ralf Laemmel wrote:
Graham Klyne wrote:
I'm trying to figure if there's any way I can use (say) monads to collect values from a Functor.
For example, suppose I have a tree of some values that supports fmap, is there any way I can use the fmap function to collect a list of all the node values?
Rather than using fmap, why not use gmap in GHC. Using an appropriate generic traversal scheme, say listify, all the code you write is the following expression:
listify (const True) mytree :: [Int]
if you are looking for all the Ints in mytree = Fork (Leaf 42) (Fork (Leaf 88) (Leaf 37)) So this would give you [42,88,37].
(So you do not need to force your datatypes to become functors, neither do you write Functor instances.)
I added this example to the boilerplate page. http://www.cs.vu.nl/boilerplate/
Ralf
-- Ralf Laemmel VU & CWI, Amsterdam, The Netherlands http://www.cs.vu.nl/~ralf/ http://www.cwi.nl/~ralf/
------------------- Graham Klyne <GK@NineByNine.org> PGP: 0FAA 69FF C083 000B A2E9 A131 01B9 1C7A DBCA CB5E
participants (8)
-
Ashley Yakeley -
Graham Klyne -
Graham Klyne
-
Hal Daume III -
Ralf Hinze -
Ralf Laemmel -
Tom Pledger -
Tomasz Zielonka