Hi,
i am replying to a thread called Data.List permutations on ghc-
users and a thread called powerSet = filterM (const [True,
False]) ... is this obfuscated haskell? on haskell cafe.
On 04.08.2009, at 19:48, Slavomir Kaslev wrote:
A friend mine, new to functional programming
The M is the list, i.e. nondeterminism monad. For each element in
the list, there is one return value where it appears (True), and one
where it does not (False).
This discussion made Curry [1] programmers realise the beauty of non-
determinism and lead to interesting reformulations of
perms = sortByM (const [True,False])
This doesn't seem right, since the comparison function is inconsistent
and moreover the results will depend on the sorting algorithm chosen.
Ganesh
===
Please access the attached
On Tue, Jul 28, 2009 at 10:58:53AM +0200, Sebastian Fischer wrote:
tails = dropWhileM (const [True,False])
Actually this should be
tails = dropWhileM (const [False, True])
--
Felipe.
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
On Jul 28, 2009, at 11:06 AM, Sittampalam, Ganesh wrote:
perms = sortByM (const [True,False])
This doesn't seem right, since the comparison function is inconsistent
I was also wary about this point, e.g. QuickSort depends on
transitivity.
and moreover the results will depend on the
Sebastian Fischer wrote:
On Jul 28, 2009, at 11:06 AM, Sittampalam, Ganesh wrote:
perms = sortByM (const [True,False])
and moreover the results will depend on the sorting algorithm chosen.
Is it only that different sorting algorithms enumerate all
permutations in different orders or is
On Tue, Jul 28, 2009 at 6:47 AM, Sebastian
Fischers...@informatik.uni-kiel.de wrote:
perms = sortByM (const [True,False])
Hence, perm as defined above can yield a list that contains all permutations
of the input (at least once) regardless of the sorting algorithm.
Where is the hitch?
The
on haskell reddit today
powerSet = filterM (const [True, False])
is said to be beautiful / mind blowing. I just don't get it. I can
play with transformations until I get
powerSet [] = [[]]
powerSet (x:xs) =
let pxs = powerSet xs
in map (x:) pxs ++ pxs
which is understandable to me
On Fri, Jul 17, 2009 at 1:35 AM, Thomas Hartman tphya...@gmail.com wrote:
on haskell reddit today
powerSet = filterM (const [True, False])
The M is the list, i.e. *nondeterminism* monad. For each element in the
list, there is one return value where it appears (True), and one where it
does
For each item, we ignore what the item actually is (hence `const`),
and say that we both want it (True) and don't want it (False) in the
output. Since we are using the list monad we are allowed to say this,
and the filter function gives us a list of lists. I think there's
probably a more intuitive
Thomas Hartman wrote:
on haskell reddit today
powerSet = filterM (const [True, False])
Does it help if we inline the 'const' function and rewrite [True, False]
in monadic notation as (return True `mplus` return False)?
powerSet = filterM (\x - return True `mplus` return False).
You can
On Jul 17, 2009 1:40pm, Thomas Hartman wrote:
my question to all 3 (so far) respondants is, how does your
explanation explain that the result is the power set?
I guess you forgot to reply to the cafe.
Well, to me the modified definition I posted looks like the essence of
powerset, the set
2009/7/17 Gleb Alexeyev gleb.alex...@gmail.com:
On Jul 17, 2009 1:40pm, Thomas Hartman wrote:
my question to all 3 (so far) respondants is, how does your
explanation explain that the result is the power set?
Because powerset(s) = 2^s?
I was going to make some nice code but I ended up
Thomas Hartman wrote:
on haskell reddit today
powerSet = filterM (const [True, False])
is said to be beautiful / mind blowing.
Is this a uniquely haskell obfu, or is there a way of reading this
definition that makes sense?
To me, these are more obvious:
powerSet = map catMaybes . mapM
The following seems to be a faster version of powerset that delivers
results strictly in the order of increasing cardinality (i.e., all
sets of size 1 first, then of size 2, etc). It seems to run faster
than any other ordered version of powerset posted so far. On GHCi,
length $ powerset [1..22
The following seems to be a faster version of powerset that delivers
results strictly in the order of increasing cardinality (i.e., all
sets of size 1 first, then of size 2, etc). It seems to run faster
than any other ordered version of powerset posted so far. On GHCi,
length $ powerset [1
powerset :: [a] - [[[a]]]
powerset [] = [[[]]]
powerset (x:xs) = [[]] : myzip x (powerset xs)
myzip :: a - [[[a]]] - [[[a]]]
myzip x [a] = [map (x:) a]
myzip x (a:b) = (map (x:) a ++ head b) : myzip x b
I suggest the above version for a sorted powerset. The result keeps a
further nesting of lists
At 18:44 05/06/03 +0100, Liyang HU wrote:
I'd just about figured the ShowS idea, but I've yet to get a handle on
this
idea of [a] 'monoid'.
Might http://www.engr.mun.ca/~theo/Misc/haskell_and_monads.htm be of any
help?
Ah, thanks. I see:
[[
A monoid is an algebraic structure consisting of a
At 19:50 04/06/03 -0400, Derek Elkins wrote:
foldl (++) [] [ combinations n as | n - intRange 1 (length as)
]
*cries out in pain and horror* fold_l_ (++) over combinatorially large
lists! (++) has gotten a reputation for being slow.
(++) isn't slow in and of itself, even using it a
At 20:25 05/06/03 -0700, Mark P Jones wrote:
Or, if duplicated computation offends you, replace (++) in the
original version of powerset with an interleave operator:
powerset :: [a] - [[a]]
powerset [] = [[]]
powerset (x:xs) = xss /\/ map (x:) xss
where xss
Hi Graham,
On Wed, Jun 04, 2003 at 12:08:38PM +0100, Graham Klyne wrote:
I thought this may be a useful exercise to see how well I'm picking up on
functional programming idioms, so I offer the following for comment:
foldl (++) [] [ combinations n as | n - intRange 1 (length as) ]
By
At 15:08 04/06/03 +0100, Liyang HU wrote:
A key point is to try and think of how you can relate one case of the
problem to a simpler instance of the same problem, rather than tackling it
head on.
I think that's a good idea to hang on to. Sometimes easier to say than to
do, it seems.
Thanks,
#g
to each or not. This
doubles the number of sets. Hence:
powerset :: [a] - [[a]]
powerset [] = [[]]
powerset (x:xs) = xss ++ map (x:) xss
where xss = powerset xs
Neat!
It happens that for the application I have in mind, it is important to
generate shorter subsets first, as the required
), you actually use more memory
at once.
Try it if you don't believe me. Test it with this program, using
each definition of powerset:
summer :: [[a]] - Integer
summer xss = foldl' (\xs r - r + toInteger (length xs)) 0 xss
n :: Int
n = 32
main :: IO
24 matches
Mail list logo
