How to write this function idiomatically?

Question

I am looking for a function that checks a predicate on list items, creates a new list for each item that satisfies the predicate, and applies the function only to that item.

Example:

someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] someFunction = ... let ys = someFunction isOdd (* 2) [1..10] {- ys == [[2, 2, 3, 4, 5, ...], [1, 2, 6, 4, 5, ...], [1, 2, 3, 4, 10, ...], ...] -} 

In ys first list is equal to the original, with the exception of the first element, which satisfies the predicate and is multiplied by 2 . The second list is also equal to the original, with the exception of the third element, etc.

I was able to write such a function by taking indexes of values ​​that satisfy a predicate and then displaying through indexes. However, this does not seem very functional, and I would like to see a more idiomatic approach.

Answer 1

You can use your finger (for example, zipper : D you move your finger across each element: D, as when reading)

 someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] someFunction check f xs = r [] xs where r _ [] = [] r ps (y:ys) = let rs = r (ps ++ [y]) ys in if check y then [ps ++ [fy] ++ ys] ++ rs else rs 

r function accepts ps "processed elements" and (y:ys) "pending elements".

If you need linear cost ( ps ++ [y] operation makes it cuadratic), use an efficient tail insertion structure.

Using splitAt you can write

 someFunction check f xs = map (\(a,(x:b)) -> a ++ [fx] ++ b) $ filter (check.head.snd) [splitAt n xs | n <- [0..length xs - 1]] 

Or using list comprehension

 someFunction check f xs = [ a ++ [fx] ++ b | n <- [0..length xs - 1] , let (a, (x:b)) = splitAt n xs , check x] 

Using the zip proposed by @chi, the solution takes a linear cost (generating lists, finally, O (n ^ 2))

 someFunction check f xs = [ a ++ [fx] ++ b | (a, (x:b)) <- init $ zip (inits xs) (tails xs) , check x] 

Finally, (?) @ ØrjanJohansen notice to remove init $ (I keep both versions, I think this is a great example)

Avoidance init $

 someFunction check f xs = [ a ++ [fx] ++ b | (a, (x:b)) <- zip (inits xs) (tails xs) , check x] 

last (xs, []) The "zipped" element is excluded from the list comprehension, @ ØrjanJohansen indicated here how it is translated

 [e | p <- l, Q] = let ok p = [e | Q] ok _ = [] in concatMap ok l 

(thanks @WillNess)

Answer 2

You can assemble this function from parts that are standard or should be. The accepted answer has the correct idea of ​​lightning. My answer about differentiation and comonads gives a general relation to the relevant operations, but let me be specific here.

I define the type of "single-hole item lists" as follows:

 data Bwd x = B0 | Bwd x :< x deriving Show type HoleyList x = (Bwd x, [x]) 

Strictly speaking, I don’t need to enter reverse lists to do this, but I am so easily embarrassed if I have to redo things in my head. (It so happened that HoleyList is a formal derivative of [] .)

Now I can determine what it should be a list item in its context.

 type InContext x = (HoleyList x, x) 

The idea is that the second component of the pair belongs between the reverse list and the direct list. I can define a function that combines the list together ( upF is upF in the general treatment.)

 plug :: InContext x -> [x] plug ((B0, xs), y) = y : xs plug ((xz :< x, xs), y) = plug ((xz, y : xs), x) 

I can also define a function that gives all the ways to split a list ( downF , in general).

 selections :: [x] -> [InContext x] selections = go B0 where go xz [] = [] go xz (x : xs) = ((xz, xs), x) : go (xz :< x) xs 

note that

 map snd (selections xs) = xs map plug (selections xs) = map (const xs) xs 

And now it’s good for us to follow the Bartek recipe.

 selectModify :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] selectModify pf = map (plug . (id *** f)) . filter (p . snd) . selections 

That is: filter the selection as a result of the test, apply the function to the element in focus, then reconnect it. If you have equipment for a zipper, it is single-line, and it should work for any differentiable functor, not just lists! The task is completed!

 > selectModify ((1 ==) . (`mod` 2)) (2*) [1..10] [[2,2,3,4,5,6,7,8,9,10] ,[1,2,6,4,5,6,7,8,9,10] ,[1,2,3,4,10,6,7,8,9,10] ,[1,2,3,4,5,6,14,8,9,10] ,[1,2,3,4,5,6,7,8,18,10]] 

Answer 3

How about this:

Start with the list:

 [1,2,3,4] 

Copy the list n times, n is its size ( :: [[]] ):

 [ [1,2,3,4], [1,2,3,4], [1,2,3,4], [1,2,3,4] ] 

Divide the lists into each element (more or less "diagonally") ( :: [([], [])] ):

 [ ([],[1,2,3,4]), ([1],[2,3,4]), ([1,2],[3,4]), ([1,2,3],[4]) ] 

Filter the lines on which head . snd head . snd does not satisfy your predicate

 [ ([], [1,2,3,4]), ([1,2], [3,4]) ] 

Apply your function to the remaining heads

 [ ([], [2,2,3,4]) ([1,2], [6,4]), ] 

Merge pairs back

 [ [2,2,3,4], [1,2,6,4] ] 

Answer 4

Looking through all the interesting and mostly somewhat bizarre solutions posted here (including @josejuan last zip , based on what is essentially an idiom that I would use in a hurry), I can't help but feel that the list is skipping really straightforward but still an idiomatic solution using explicit, lazy recursion is the type of code you'll probably see in standard libraries if someFunction was a standard function. So, here is the version of this (including the go stolter, which you will also see):

 someFunction :: (a -> Bool) -> (a -> a) -> [a] -> [[a]] someFunction pf xs = go xs where go [] = [] go (x:xs) | px = (fx : xs) : rest | otherwise = rest where rest = map (x :) (go xs)