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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

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

Erik Quaeghebeur
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
Reply | Threaded
Open this post in threaded view
|

generating the set of all finite-valued ...

Erik Quaeghebeur
> 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
Reply | Threaded
Open this post in threaded view
|

generating the set of all finite-valued ...

Jan Jakubuv-2
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.

Reply | Threaded
Open this post in threaded view
|

generating the set of all finite-valued ...

Brent Yorgey-2
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
Reply | Threaded
Open this post in threaded view
|

generating the set of all finite-valued ...

Erik Quaeghebeur
>> 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
Reply | Threaded
Open this post in threaded view
|

generating the set of all finite-valued [...]

Erik Quaeghebeur
In reply to this post by Erik Quaeghebeur
> 2009/4/23 Erik Quaeghebeur <[hidden email]>
>
>> 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

On Mon, 27 Apr 2009, Haroldo Stenger wrote:
>
> i got curious about this one. Can you elaborate ?

Well, elaborate about my ultimate goal, or about the powerset definition?
The latter I can tell little about, I found it on-line and recognized it
as a starting point. The former: generalizing
http://users.ugent.be/~equaeghe/constraints.php to previsions from
probabilities; C++ is a little too heavy, so I thought I'd try out
Haskell.

Erik

Reply | Threaded
Open this post in threaded view
|

generating the set of all finite-valued ...

Chaddaï Fouché
In reply to this post by Erik Quaeghebeur
On Fri, Apr 24, 2009 at 6:20 PM, Erik Quaeghebeur
<[hidden email]> wrote:
> Yes, now I see it, thanks to both Jan and Brent.
> I can nicely generalize this to
>
> ? ? ? ?n = ...
> ? ? ? ?values = [...]
> ? ? ? ?sequence (replicate n values)
>

(sequence (replicate n xs)) is part of Control.Monad under the name
replicateM so :

> replicateM n values

--
Jeda?