[Haskell-cafe] where to put handy functions?

[Tillmann Rendel]

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