Re: [Haskell-cafe] Producing MinimumValue
On 7/19/07, Alexteslin [EMAIL PROTECTED] wrote: What wrong with my original solution? allEqual2 :: [Int] - Bool allEqual2 xs = length xs == length (filter isEqual xs) where isEqual n = (head xs) == n It looks simpler to me I believe it's correct, but the use of length and filter seems forced. For example, for a very long list that has the second element mismatch, the versions with explicit recursion (or fold variants) will terminate with False as soon as a mismatch is found; the length version will not terminate until both have been fully traversed. If you're allowed to use everything, perhaps the clearest would be: allEqual3 [] = True allEqual3 (x:xs) = all (== x) xs (with all built on top of a fold.) Colin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Construct all possible trees
On 6/12/07, Andrew Coppin [EMAIL PROTECTED] wrote: Based on the sample output, I'm guessing that the desired output is every tree which, when flattened, gives a permutation of a non-empty subset of the supplied list. This limits the output to trees with up to n leaves. Branch (Branch (Leaf 1) (Leaf 3)) (Leaf 1), If I'm guessing the desired output correctly, this must be a typo? I'd be tempted to solve the list-only problem first (generate all sub-permutations of a list), then solve the tree problem (generate all un-flattenings of a list). Colin DeVilbiss ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] k-minima in Haskell
On 4/13/07, Ian Lynagh [EMAIL PROTECTED] wrote:
Tuple each element with its position: O(n)
Find kth smallest element in linear time, as per [1]: O(n)
Filter list for elements = kth smallest: O(n)
Sort filtered list by position: O(k log k)
map snd to get the positions: O(k)
Total: O(n + k log k)
[1] http://en.wikipedia.org/wiki/Selection_algorithm
Inspired by the above, I thought I'd see about writing it.
Note that attaching the indices prevents equal items from
comparing equal. I didn't feel like writing the code for a
special data type that ignored a second element for the
purposes of comparisons; that just means replacing
zip and map send.
The user can add stability by selective use of reverse
within the continuation functions.
There should probably be strictness annotations somewhere,
and calls to length should probably be accumulated in
partition instead, but the idea should be sound (except for
the likelihood of a bad pivot).
partition cont _ [] lt eq gt = cont lt eq gt
partition cont p (x:xs) lt eq gt = case x `compare` p of
LT - partition cont p xs (x:lt) eq gt
EQ - partition cont p xs lt (x:eq) gt
GT - partition cont p xs lt eq (x:gt)
qsort [] = []
qsort (x:xs) = partition qs' x xs [] [x] []
where qs' lt eq gt = qsort lt ++ (eq ++ qsort gt)
findfirst _ [] = []
findfirst k (x:xs) = partition ff' x xs [] [x] []
where
ff' lt eq gt = let { ll = length lt; lle = ll + length eq }
in if k ll then findfirst k lt
else if k lle then lt ++ eq ++ findfirst (k - lle) gt
elselt ++ take (k - ll) eq
getSmallest k = qsort . findfirst k
getSmallestIndices k = map snd . getSmallest k . flip zip [0..]
___
Haskell-Cafe mailing list
[EMAIL PROTECTED]
http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Default (or empty) values
On 1/17/07, Max Vasin [EMAIL PROTECTED] wrote: Fields of the Book datatype which are not (Maybe a) are required to be present. This doesn't actually answer your question, but if those fields are really required and you want to avoid the possibility of a default value sneaking into the program through a bug, you may prefer to use undefined instead of a non-bottom value for the required fields. That is, Book undefined undefined Nothing Nothing Nothing undefined undefined undefined (lots of typing, but if a bug slips in and you get a partially-defined book into the guts of the program, you'll die instead of silently using invalid data.) class Empty e where empty :: e But still I have to emplement instances by hand. What would the strategy be here for automatically defining the instances? For example, what are the Empty instances for data Foo = Bar | Baz | Quux data Foo2 = Bar2 Int | Baz2 String | Quux2 (Maybe String) Or may be it would be better to drop out Empty and use something else? I see no inherent problem with Empty, just with the automated instantiation. Then again, I'd be tempted to wait to define Empty until I saw the second or third instance of its use. Colin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] beginner's problem about lists
On 10/10/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: I'm trying to implement a function that returns the shorter one of two given lists, something like shorter :: [a] - [a] - [a] However, it becomes difficult when dealing with infinite lists, for example, shorter [1..5] (shorter [2..] [3..]) Could this evaluate to [1..5]? I haven't found a proper implementation. If you can figure out a solution that works for both shorter [1..5] [2..] and shorter [2..] [1..5], the essence of that solution will work to define a shortest [[1..5],[2..],[3..]] (leaving shorter a b = shortest [a, b]). As shown elsewhere in the thread, there is at least one solution with slightly different type signatures that works much like you want; something like: unFoo (shorter' (foo a) (shorter' (foo b) (foo c))) Colin ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] List-to-outline
On 2/14/06, Steve Schafer [EMAIL PROTECTED] wrote: isChild :: Int - Node - Bool isChild i (Nd j _) = (j i) isChild _ _ = False prepend :: Int - [Node] - [Node] prepend i [] = [Nd i []] prepend i ns = (Nd i f):s where (f,s) = span (isChild i) ns unflatten :: [Int] - [Node] unflatten ns = foldr prepend [] ns The following seemed a little more natural to me: unflatten [] = [] unflatten (x:xs) = (Node x $ unflatten xh) : unflatten xt where (xh, xt) = span (x) xs That is, a node containing the first item and the hierarchy of all of its children, followed by the hierarchies of its siblings. Is [0,2,1,2] invalid input? The behavior of both versions puts the first 2 and the 1 as children of the root, but the second 2 is a child of the 1. Colin DeVilbiss ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] class Ref...
On 6/8/05, Gracjan Polak [EMAIL PROTECTED] wrote: Tomasz Zielonka wrote: On Tue, Jun 07, 2005 at 12:25:50PM +0200, Gracjan Polak wrote: To put it another way: is Data.Map only workaround to get something done, or is it The Right Way of doing PQs in Haskell? Another option is to look at Chris Okasaki's _Purely_Functional_Data_Structures_ (code available at his website). Pairing heaps and splay heaps (when bootstrapped) are said to have O(1) in everything but removeMin (new, insert, merge, findMin) and good constant factors. Colin DeVilbiss ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
