CODEWITHSUNDEEP
listhaskellrecursion
user5672248
user5672248

Reputation:

Haskell all possible ways to remove 1 element from the list

This is what I've written so far, but I've gotten a bit lost:

removeone :: [a] -> [[a]]
removeone [] = []
removeone (a:as) = [as] -- I'm lost here

This is the kind of output I'm looking for:

removeone [1,2,3] = [[2,3],[1,3],[1,2]]
removeone [1,2]   = [[1],[2]]

What would be the best way to solve this problem? In Java I would just loop this and each time produce a new list that I would append to a pre-existing list. I am pretty lost in translating this into Haskell.

Upvotes: 0

Views: 642

Answers (2)

samsergey
samsergey

Reputation: 228

The idiomatic recursive solution is given by @сhepner. However, everyday Haskell is not about recursion, it's more about recursive patterns and precise formulation of a problem. If I have got it I would end up with following solution

import Data.List (inits, tails)

removeone :: [a] -> [[a]]
removeone lst = zipWith (++) (inits lst) (tail (tails lst))

It is more then 2× faster then explicit recursion and seems more like formulation of a problem. Using "dangerous" function tail is safe here because tails [] = [[]]. Trivial cases are held by zipWith, inits and tails.

If the resulting complementary lists are supposed to be nontrivially processed (say, they represent a view of each game personage in a group) consider Zippers and utilize their comonadic properties (it is really not as scaring as it sounds:)).

Upvotes: 3

chepner
chepner

Reputation: 530950

Let's look at a slightly longer example and figure out how to break it up:

> removeone [1,2,3,4]
[[2,3,4],[1,3,4],[1,2,4],[1,2,3]]

As you already guessed, you simply put as (the result of removing the first element from the input) on the front of some list, but what list is that?

removeone (a:as) = as : ...

Looking more closely, you can see that a == 1 is at the front of each of them. Let's factor that out to see how we might construct it:

[[1,3,4],[1,2,4],[1,2,3]] == [1:[3,4],1:[2,4],1:[2,3]]
                          == map (1:) [[3,4],[2,4],[2,3]]

The second argument should look familiar: it's what you should expect the result of removeone [2,3,4] to look like. And just like that, you have your recursive case:

removeone (a:as) = as : map (a:) (removeone as)

Upvotes: 5

Related Questions