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