CODEWITHSUNDEEP
haskellfunctional-programming
Cameron Martin
Cameron Martin

Reputation: 6012

Convert a function returning a list to a list of functions

I have a function f :: Int -> [a] which always returns a list of size n, like so:

f 0 = [a_0_1, a_0_2, ..., a_0_n]
f 1 = [a_1_1, a_1_2, ..., a_1_n]
.
.
.
f k = [a_k_1, a_k_2, ..., a_k_n]

I want to transform this into a list of functions:

[f_1, f_2, ..., f_n] :: [Int -> a]

where

f_k i = a_i_k

I hope the notation I've used is clear enough to convey what I want.

Upvotes: 1

Views: 216

Answers (5)

effectfully
effectfully

Reputation: 12715

If you have

f 0 = [a_0_0, a_0_1 ... a_0_m]
f 1 = [a_1_0, a_1_1 ... a_1_m]
...
f n = [a_n_0, a_n_1 ... a_n_m]

then

matr = transpose $ map f [0..n]

gives you

[ [a_0_0, a_1_0 ... a_n_0]
, [a_0_1, a_1_1 ... a_n_1]
...
, [a_0_m, a_1_m ... a_n_m]
]

Your equation is f_j i = a_i_j, where i ranges over [0..n] and j ranges over [0..m].

Since, matr is transposed, the equation becomes f_j i = matr_j_i, which can be reflected as follows:

map (\j i -> matr !! j !! i) [0..]

The whole function is

transform f n = map (\j i -> matr !! j !! i) [0..] where
    matr = transpose $ map f [0..n]

Or just

transform f n = map (!!) $ transpose $ map f [0..n]

EDIT

As @josejuan pointed out, this code is not efficient, since, while evaluating

(transform f n !! j) i

transpose forces f i' for all i' <= i.

Upvotes: 1

AJF
AJF

Reputation: 11913

This is a good question, and deserves to be applied to an arbitrary function of general type a -> [b].

I actually made a related question about the monadic sequence function, regarding making an opposite, an unsequence function. It was shown to be impossible. Here's why:

When a function returns a list, it may be of an arbitrary length. This means that we can only determine the length of the returned list when we call the function. As a result, we cannot make a list of fixed length without calling the function.

A simpler way of understanding this is imagining that we've got values trapped in an IO monad. of type IO [Int]. This is perfectly comparable to a -> [Int] because both values can only be manipulated while they're kept inside their monadic type. This is different for the sequence :: Monad m => [m a] -> m [a] because the [a] monad can be deconstructed, i.e: it's a comonad too.

To put it simply, 'pure' monads can only be constructed, and thus you cannot take a list's length, which is fundamental if we are to construct a list, from inside a function monad, or and IO monad. I hope this helps you!

Upvotes: 1

dfeuer
dfeuer

Reputation: 48581

Let's start by actually applying the function to all these values:

listf = map f [0..k]

So

listf = [[a_0_1, a_0_2, ..., a_0_n]
        ,[a_1_1, a_1_2, ..., a_1_n]
        ,...
        ,[a_k_1, a_k_2, ..., a_k_n]]

Now we have a list of lists, but it's the wrong way around. So let's take the transpose:

listft = transpose listf

listft = [[a_0_1, a_1_1, ..., a_k_1]
         ,[a_0_2, a_1_2, ..., a_k_2]
         ,...
         ,[a_0_n, a_1_n, ..., a_k_n]]

Now we have a list of lists, and each of the inner lists represents an f_i for some i. But we don't want to stop with that representation, because actually calculating the jth element of a list is O(j). So let's use Vector, from Data.Vector, instead:

listmapsf = map fromList listft

Now we have a list of Vectors, each of which represents an f_i. We can turn those into functions using !:

functions = map (!) listmapsf

Note: this does absolutely nothing to verify that the input lists are all the same length. It's probably also not the most efficient way to produce the list of functions, but it's not a bad one.

Edit: per user3237465's suggestion, I've replaced the IntMap representation with a Vector one.

Upvotes: 1

karakfa
karakfa

Reputation: 67467

If you don't need all of the values don't compute them until they are needed. You just need to define indexed access, i.e. let frc r c = f!!r!!c where r is the row and c is the column.

Upvotes: 0

josejuan
josejuan

Reputation: 9566

Use lambdas

fn = [(\k -> (f k)!!i) | i <- [0..n - 1]]

then

[f1, f2, f3, ...] = fn

but you should analyze your general problem (this approach is slow).

Complete sandbox code:

n = 5

f k = [2 * k + i | i <- [1..n]]

fn = [(\k -> (f k)!!i) | i <- [0..n - 1]]

(f1:f2:_) = fn

main = do

    print $ f 4
    print $ (fn!!3) 4
    print $ f2 4

Upvotes: 1

Related Questions