# generating the set of all finite-valued functions on a finite space

7 messages
Open this post in threaded view
|

## generating the set of all finite-valued functions on a finite space

 Hi, I'd like to lazily generate the set of all {-1,0,1}-valued functions on {'a','b','c'}? How should I best approach this. I was thinking about generalizing the power set definition powerset :: [a] -> [[a]] powerset = filterM (const [True, False]) but clearly don't know enough about filterM and the like to do it this way. Erik
Open this post in threaded view
|

## generating the set of all finite-valued ...

 > On Thu, Apr 23, 2009 at 03:45:27PM +0200, Erik Quaeghebeur wrote: >> >> I'd like to lazily generate the set of all {-1,0,1}-valued functions on >> {'a','b','c'}? How should I best approach this. I was thinking about >> generalizing the power set definition On Thu, 23 Apr 2009, Jan Jakubuv wrote: > > Try to start with this: > >    mapM (\x -> [(x,-1),(x,0),(x,1)]) ['a','b','c'] Aha. Great. Thanks, Jan. And now I realized that I don't really care about the domain, so I said: Prelude> let m = mapM (\x -> [(x,-1),(x,0),(x,1)]) ['a','b','c'] Prelude> map (\x -> snd \$ unzip x) m [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]] Any more direct way of doing this? (Still trying to understand how the mapM works... I've found it's sequence.map, but that doesn't really help.) The next step will be to choose a good data format for what I'm trying to achieve. The functions (now represented as lists) would more naturally be represented as column matrices, e.g., from Numeric.LinearAlgebra of hmatrix, as I'll be needing some linear system solver. I can do the transition from lists to that, but I'm afraid they don't give me the necessary flexibility; I'd need to filter them based on (maximum/minimum) component values and sum them and such. Any thoughts on that? Erik
Open this post in threaded view
|

## generating the set of all finite-valued ...

 On Fri, Apr 24, 2009 at 12:16:06AM +0200, Erik Quaeghebeur wrote: > > Aha. Great. Thanks, Jan. And now I realized that I don't really care > about the domain, so I said: > > Prelude> let m = mapM (\x -> [(x,-1),(x,0),(x,1)]) ['a','b','c'] > Prelude> map (\x -> snd \$ unzip x) m > [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]] > > Any more direct way of doing this? (Still trying to understand how the   > mapM works... I've found it's sequence.map, but that doesn't really > help.) > Well, you can write:     mapM (const [-1,0,1]) [1..3] mapM takes a function which returns a computation for a given argument. In this case the function always returns the computation [-1,0,1] which you can think of as a non-deterministic computation resulting in either -1, or 0, or 1. This computation is executed for every value in the list [1..3] and because this list has three values the execution results in [x,y,z] where each of x, y, and z is either -1, or 0, or -1. This gives you all variations. You can also write:     [[x,y,z] | x<-[-1,0,1], y<-[-1,0,1], z<-[-1,0,1]] Sincerely,     Jan. -- Heriot-Watt University is a Scottish charity registered under charity number SC000278.
Open this post in threaded view
|

## generating the set of all finite-valued ...

 On Fri, Apr 24, 2009 at 11:36:44AM +0100, Jan Jakubuv wrote: > On Fri, Apr 24, 2009 at 12:16:06AM +0200, Erik Quaeghebeur wrote: > > > > Aha. Great. Thanks, Jan. And now I realized that I don't really care > > about the domain, so I said: > > > > Prelude> let m = mapM (\x -> [(x,-1),(x,0),(x,1)]) ['a','b','c'] > > Prelude> map (\x -> snd \$ unzip x) m > > [[-1,-1,-1],[-1,-1,0],[-1,-1,1],[-1,0,-1],[-1,0,0],[-1,0,1],[-1,1,-1],[-1,1,0],[-1,1,1],[0,-1,-1],[0,-1,0],[0,-1,1],[0,0,-1],[0,0,0],[0,0,1],[0,1,-1],[0,1,0],[0,1,1],[1,-1,-1],[1,-1,0],[1,-1,1],[1,0,-1],[1,0,0],[1,0,1],[1,1,-1],[1,1,0],[1,1,1]] > > > > Any more direct way of doing this? (Still trying to understand how the   > > mapM works... I've found it's sequence.map, but that doesn't really > > help.) > > > > Well, you can write: > >     mapM (const [-1,0,1]) [1..3] Better yet (in my opinion), you can just write       sequence (replicate 3 [-1,0,1]) which is really the same thing, since mapM = sequence . map.  Mapping (const [-1,0,1]) over [1..3] yields [[-1,0,1], [-1,0,1], [-1,0,1]], that is, (replicate 3 [-1,0,1]).  It's the 'sequence' that does the magic of selecting an item from each of the three lists in all possible ways. -Brent
Open this post in threaded view
|

## generating the set of all finite-valued ...

 >> On Fri, Apr 24, 2009 at 12:16:06AM +0200, Erik Quaeghebeur wrote: >>> >>> m = mapM (\x -> [(x,-1),(x,0),(x,1)]) ['a','b','c'] >>> map (\x -> snd \$ unzip x) m >>> >>> Any more direct way of doing this? > On Fri, Apr 24, 2009 at 11:36:44AM +0100, Jan Jakubuv wrote: >> >> Well, you can write: >> >>     mapM (const [-1,0,1]) [1..3] On Fri, 24 Apr 2009, Brent Yorgey wrote: > > Better yet (in my opinion), you can just write > >      sequence (replicate 3 [-1,0,1]) > > which is really the same thing, since mapM = sequence . map.  Mapping > (const [-1,0,1]) over [1..3] yields [[-1,0,1], [-1,0,1], [-1,0,1]], > that is, (replicate 3 [-1,0,1]).  It's the 'sequence' that does the > magic of selecting an item from each of the three lists in all > possible ways. Yes, now I see it, thanks to both Jan and Brent. I can nicely generalize this to   n = ...   values = [...]   sequence (replicate n values) My ideas about how I should approach other aspects of my programming task are also crystallizing. Now find a nice stretch of time to work things out... Erik