Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 common list functions [2]. Here are some of them translated to Haskell: inits = takeWhileM (const [True,False]) tails = dropWhileM (const [True,False]) perms = sortByM (const [True,False]) Only that Hoogle does not know any of these monadic helper functions. Cheers, Sebastian [1]: http://www.curry-language.org/ [2]: unfortunately not yet in the mailing list archive (http://www.informatik.uni-kiel.de/~mh/curry/listarchive/ Thread title: beautiful non-determinism) -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html === ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 sorting algorithm chosen. Is it only that different sorting algorithms enumerate all permutations in different orders or is there a sorting algorithm, such that the above definition does not enumerate all permutations? Here is some shirt-sleeved reasoning: Every sorting algorithm :: [Int] - [Int] that actually sorts can describe every possible permutation (if there is a permutation that cannot be realised by the sorting algorithm then there is an input list that cannot be sorted). Hence, if this sorting algorithm is `sortBy p` for some predicate p then there are possible decisions of p to produce every possible permutation. If p makes *every* decision non- deterministically then certainly the specific decisions necessary for any specific permutation are also made. 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? Sebastian -- Underestimating the novelty of the future is a time-honored tradition. (D.G.) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
RE: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 there a sorting algorithm, such that the above definition does not enumerate all permutations? [..] 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 at least once bit - unless your non-determinism is based on set rather than bag semantics, it's wrong to duplicate results. Ganesh === Please access the attached hyperlink for an important electronic communications disclaimer: http://www.credit-suisse.com/legal/en/disclaimer_email_ib.html === ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 algorithm might diverge when given a non-transitive comparison operator. On Spore we had a bug where a NaN got into a list of floats we were sorting and our quicksort corrupted the heap because isn't transitive on lists with NaNs. -- ryan ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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, but no matter how long I look at the original filterM definition it just doesn't click. Is this a uniquely haskell obfu, or is there a way of reading this definition that makes sense? If anybody agrees with me, care to throw out other examples of obfuscated haskell considered harmful? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 not (False). Basically, regular filter says that for each element in the list, we need to make a choice as to whether it occurs in the result. Here we use nondeterminism to make both choices. Luke 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, but no matter how long I look at the original filterM definition it just doesn't click. Is this a uniquely haskell obfu, or is there a way of reading this definition that makes sense? If anybody agrees with me, care to throw out other examples of obfuscated haskell considered harmful? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 name for `filterM`... ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] powerSet = filterM (const [True, False]) ... is this obfuscated haskell?
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 ((mzero:).return.return) powerSet = map concat . mapM ((mzero:).return.return) They work by pretty much the same principle. Perhaps they seem simpler to me only because I use mapM a lot more than I use filterM. Regards, Yitz ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
