On Thu, Aug 09, 2007 at 02:29:50PM -0700, Chad Scherrer wrote:

Is there process for submitting functions for consideration for inclusion into future versions of the standard libraries? For example, I'd like to see this in Data.List:

extract :: [Int] -> [a] -> [a] extract = f 0 where f _ _ [] = [] f _ [] _ = [] f k nss@(n:ns) (x:xs) = if n == k then x:f (k+1) ns xs else f (k+1) nss xs

This behaves roughly as extract ns xs == map (xs !!) ns

except that it's a lot more efficient, and it still works if ns or xs (but not both) are infinite. Oh, and "ns" are required to be ordered and non-negative.

I'm guessing there are a lot of similarly simple handy functions, and I'm wondering if there's anything in place to avoid (1) reinventing the wheel, and (2) name clashes. Someone else may have written "extract" as well, meaning one of us wasted our time. And chances are, if they did, it has a different name, leading to forced qualified imports.

Finally, even if no one else is using it, it would be good to settle on reasonable names for things more easily. Is there a better name for this function? Is there a reason not to call it "extract"?

http://www.haskell.org/haskellwiki/Library_submissions Stefan

On 8/9/07, Chad Scherrer wrote:

extract :: [Int] -> [a] -> [a] extract = f 0 where f _ _ [] = [] f _ [] _ = [] f k nss@(n:ns) (x:xs) = if n == k then x:f (k+1) ns xs else f (k+1) nss xs

This behaves roughly as extract ns xs == map (xs !!) ns

except that it's a lot more efficient, and it still works if ns or xs (but not both) are infinite. Oh, and "ns" are required to be ordered and non-negative.

Nifty function there. =) And for the record, it works just fine if both lists are infinite -- it just produces an infinite output list, but it's lazy so no problem: *Main> take 10 $ extract [1,3..] [2..] [3,5,7,9,11,13,15,17,19,21] -Brent

Chad Scherrer wrote:

extract :: [Int] -> [a] -> [a]

[...]

This behaves roughly as extract ns xs == map (xs !!) ns

extract sounds like removing the elements to be extracted from the original list. I would therefore expect it's type signature to be extract :: [Int] -> [a] -> ([a], [a]) with extract [0, 2] "abcde" == ("ac", "bde"). For your extract I would prefer "select" as name, in analogy to relational algebra, viewing a list as a one-column table.

Oh, and "ns" are required to be ordered and non-negative.

Non-negative is obvious for a list of indexes. Ordered makes sense implementation-wise, and should be easy to match for many applications. But is it a sensible constraint on a standard library function? For Data.List, I would prefer a multi-pass select function like this: select :: Integral n => [n] -> [a] -> [a] select ns xs = select' 0 ns xs where select' k [] _ = [] select' k (n:ns) [] = select' k ns [] select' k nns@(n:ns) yys@(y:ys) = case k `compare` n of LT -> select' (succ k) nns ys EQ -> y : select' k ns yys GT -> select nns xs *Main> select [0, 2, 2, 1] "abcde" "accb" There could be selectAsc for the special case of ordered indexes, to avoid keeping the whole input list in memory. Tillmann