2

I am trying to implement a function in Haskell that'll take an arbitrary integer list xs and an integer k, and returns a set of lists with k in all possible positions.

For example, for a xs = [0, 1] and k = 2, we'd have

myFunction [0, 1] 2 = [ [2, 0, 1], [0, 2, 1], [0, 1, 2] ]

I've implemented it as 

putOn xs x i = (take i xs) ++ (x:(drop i xs))
putOnAll xs x = map (putOn xs x) [0..(length xs)]

yet, I feel there must be other smarter ways to achieve the same. My code seems like someone trying to kill a bug with a missile. Could anyone make sugestions on ways to do something clever than this bit of code?

Thanks

devoured elysium
  • 101,373
  • 131
  • 340
  • 557

4 Answers4

3

Taken from this question:

ins x []     = [[x]]
ins x (y:ys) = (x:y:ys):[ y:res | res <- ins x ys]
Community
  • 1
  • 1
sepp2k
  • 363,768
  • 54
  • 674
  • 675
3

You can use arrows, too:

import Control.Arrow

ins x = inits &&& tails >>> second (map (x:)) >>> uncurry (zipWith (++))

With &&& ("fanout") you give one argument to two functions, which gives a pair of results. You can use >>> ("and then") to switch the normal application order, allowing to have left-to-right chains of operations. second works only on the second part of the pair. Finally you need an uncurry to recombine the results, feeding a pair in a function expecting two separate arguments.

Landei
  • 54,104
  • 13
  • 100
  • 195
1

I really like the clarity of this definition:

ins x ys = zipWith (\pre post -> pre ++ [x] ++ post) (inits ys) (tails ys)
luqui
  • 59,485
  • 12
  • 145
  • 204
1
ins x xs = zipWith (\ a b -> a ++ (x:b)) (inits xs) (tails xs)

[Edit] Bah, too late, luqui beat me :-)

However, here a version without lambda:

ins x xs = zipWith (flip (++).(:) x) (tails xs) (inits xs)
Landei
  • 54,104
  • 13
  • 100
  • 195