Здравствуйте, _NN_, Вы писали:

_NN>Подскажите как сделать оптимальнее и возможно правильнее.
_NN>Имеем список ,скажем , строк и функцию принимающую строку и возвращающую список строк.
_NN>На каждый элемент списка получаем список из функции и нужно его обойти и передать хвост дальше.

_NN>Скажем при данных "a", "b" и функции x => [x + "x", y + "y"] получаем все возможные варианты: [ax, bx], [ax, by], [ay, bx], [ay, by]

_NN>Вот код который этот делает. (Прощу прощения за Nemerle )
_NN>Конкретно мне не нравится acc + [h'] , этот имеет линейную сложность.

В Хаскеле есть библиотечная forM :: Monad m => [a] -> (a -> m b) -> m [b], которая ровно это делает

> forM ["a","b"] (\x->[x++"x",x++"y"])
[["ax","bx"],["ax","by"],["ay","bx"],["ay","by"]]

Но ее реализация заточена под хаскельный ленивый рантайм и оптимизатор, в частности реализована через foldr, чтобы быть "хорошим консьюмером". Замечу, что a ++ b в Хаскеле имеет линейную сложность по первому аргументу и константную по второму (реюзает санк, прицепляя второй список как хвост).