1

I am looking for an elegant solution to the following problem. I have two lists of the following types:

[Float] and, [[Float]]

The first list contains an infinite amount of random values. The second list contains values I no longer care about. Its structure is finite and must be preserved. The values of the first list needs to be replacing those of the second.

Obviously, since the first list contains random values, I do not want to use them twice. Can anyone help me do this in a clear, concise, and terse way?

scramble :: [Float] -> [[Float]] -> [[Float]]

Give me your best shot

2
  • Do you want to create a list with values from the first arguments and the structure of the second argument?
    – user395760
    Nov 27, 2011 at 15:03
  • Yes, that is exactly what I am after. Nov 27, 2011 at 15:15

3 Answers 3

9

Using the split package for splitting:

import Data.List.Split (splitPlaces)
scramble x y = splitPlaces (map length y) x
2
  • @augustss: not one that is included with GHC
    – newacct
    Nov 27, 2011 at 21:13
  • @newacct, even better then. +1
    – luqui
    Nov 28, 2011 at 0:36
8

Will this do?

flip . (evalState .) . traverse . traverse . const . state $ head &&& tail

EDIT: let me expand on the construction...

The essential centre of it is traverse . traverse. If you stare at the problem with sufficiently poor spectacles, you can see that it's "do something with the elements of a container of containers". For that sort of thing, traverse (from Data.Traversable) is a very useful gadget (ok, I'm biased).

traverse :: (Traversable f, Applicative a) => (s -> a t) -> f s -> a (f t)

or, if I change to longer but more suggestive type variables

traverse :: (Traversable containerOf, Applicative doingSomethingToGet) =>
              (s -> doingSomethingToGet t) ->
              containerOf s -> doingSomethingToGet (containerOf t)

Crucially, traverse preserves the structure of the container it operates on, whatever that might be. If you view traverse as a higher-order function, you can see that it gives back an operator on containers whose type fits with the type of operators on elements it demands. That's to say (traverse . traverse) makes sense, and gives you structure-preserving operations on two layers of container.

traverse . traverse ::
  (Traversable g, Traversable f, Applicative a) => (s -> a t) -> g (f s) -> a (g (f t))

So we've got the key gadget for structure-preserving "do something" operations on lists of lists. The length and splitAt approach works fine for lists (the structure of a list is given by its length), but the essential characteristic of lists which enables that approach is already pretty much bottled by the Traversable class.

Now we need to figure out how to "do something". We want to replace the old elements with new things drawn successively from a supply stream. If we were allowed the side-effect of updating the supply, we could say what to do at each element: "return head of supply, updating supply with its tail". The State s monad (in Control.Monad.State which is an instance of Applicative, from Control.Applicative) lets us capture that idea. The type State s a represents computations which deliver a value of type a whilst mutating a state of type s. Typical such computations are made by this gadget.

state     :: (s -> (a, s)) -> State s a

That's to say, given an initial state, just compute the value and the new state. In our case, s is a stream, head gets the value, tail gets the new state. The &&& operator (from Control.Arrow) is a nice way to glue two functions on the same data to get a function making a pair. So

head &&& tail :: [x] -> (x, [x])

which makes

state $ head &&& tail :: State [x] x

and thus

const . state $ head &&& tail :: u -> State [x] x

explains what to "do" with each element of the old container, namely ignore it and take a new element from the head of the supply stream.

Feeding that into (traverse . traverse) gives us a big mutatey traversal of type

f (g u) -> State [x] (f (g x))

where f and g are any Traversable structures (e.g. lists).

Now, to extract the function we want, taking the initial supply stream, we need to unpack the state-mutating computation as a function from initial state to final value. That's what this does:

evalState :: State s a -> s -> a

So we end up with something in

f (g u) -> [x] -> f (g x)

which had better get flipped if it's to match the original spec.

tl;dr The State [x] monad is a readymade tool for describing computations which read and update an input stream. The Traversable class captures a readymade notion of structure-preserving operation on containers. The rest is plumbing (and/or golf).

5
  • Slightly obfuscated for someone at my rudimentary level, nonetheless very elegant. Nov 27, 2011 at 15:44
  • 1
    Nice thing about this solution is that it can work on deeper lists by adding more traverse.
    – sdcvvc
    Nov 27, 2011 at 18:29
  • 2
    Thanks. That's true. This thing really ain't fussy. It's perhaps a misleading coincidence that the original problem is taking from a list and making listy structures. If you want a nice generalisation, just strip it back to one traverse, so (flip . (evalState .) . traverse . const . state $ head &&& tail) which works for any Traversable structure, not just lists. Traversable is closed under composition newtype C f g x = C (f (g x)) so you can use that fact to renegotiate two (or more) layers of container locally as one composite layer without changing the traversal machinery at all.
    – pigworker
    Nov 27, 2011 at 19:02
  • I like this solution because it is a generalization of the given problem. Nov 28, 2011 at 14:47
  • You can tidy it quite a bit if you use the MonadRandom interface to manage your random number supply. Then you're looking at some wrapper for traverse (const getRandom).
    – pigworker
    Nov 28, 2011 at 15:28
4

This is the obvious way to do it, but I take it this isn't terse enough?

scramble :: [a] -> [[a]] -> [[a]]
scramble _  [] = []
scramble xs (y : ys) = some : scramble rest ys
  where (some, rest) = splitAt (length y) xs
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.