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

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

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

using Nemerle.Collections;
using System.Console;

module Program
{
  F(l : list[string], f : string -> list[string]) : list[list[string]]
  {
    def impl(l, acc)
    {
      match(l)
      {
      | [] => [acc]
      | h :: t => f(h).Map(h' => impl(t, acc + [h'])).Flatten()
      }
    }
    
    impl(l, [])
  }
 
  Main() : void
  {
    def res = F(["a", "b"], x => [x + "x", x + "y"]);
    
    // ax, bx
    // ax, by
    // ay, bx
    // ay, by
    foreach(r in res)
      WriteLine($"..$r");
    
    _ = ReadLine();
  }
}

Map = Haskell map
Flatten = Haskell concat

Здравствуйте, _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 в Хаскеле имеет линейную сложность по первому аргументу и константную по второму (реюзает санк, прицепляя второй список как хвост).

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

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

Можно так
— из "a" получаем f("a") = ["ax", "ay"]
— из "b" получаем f("b") = ["bx", "by"]
— делаем декартово произведение полученных списков ["ax", "ay"] x ["bx", "by"] = [[ax, bx], [ax, by], [ay, bx], [ay, by]]

Не знаю как сделать декартово произведение в Nemerle, может есть функция в библиотеке (в Haskell есть).

В целом как-то так:

-- декартово произведение
-- cartesian [ ["a","b"], ["1","2"] ] = [["a","1"],["a","2"],["b","1"],["b","2"]]
cartesian [] = [ [] ]
cartesian (dim:dims) = [(e:es) | e <- dim, es <- cartesian dims]

-- искомая функция
my_list_of_list xs f = cartesian $ map f xs

-- тест
main = print $ my_list_of_list ["a","b"] (\x -> [x++"x",x++"y"])

Попробовать можно здесь: http://codepad.org/Wycro8La

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

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

Я тут подглядел исходник, но что-то не получается воссоздать этот же код через foldr

Исходник:

-- | 'forM' is 'mapM' with its arguments flipped
forM            :: Monad m => [a] -> (a -> m b) -> m [b]
{-# INLINE forM #-}
forM            = flip mapM

-- | @'mapM' f@ is equivalent to @'sequence' . 'map' f@.
mapM            :: Monad m => (a -> m b) -> [a] -> m [b]
{-# INLINE mapM #-}
mapM f as       =  sequence (map f as)

-- | Evaluate each action in the sequence from left to right,
-- and collect the results.
sequence       :: Monad m => [m a] -> m [a] 
{-# INLINE sequence #-}
sequence ms = foldr k (return []) ms
            where
              k m m' = do { x <- m; xs <- m'; return (x:xs) }



map :: (a -> b) -> [a] -> [b]
map _ []     = []
map f (x:xs) = f x : map f xs

foldr k z = go
          where
            go []     = z
            go (y:ys) = y `k` go ys

Попытка:

F2(l : list[string], f : string -> list[string]) : list[list[string]]
{
  l.Map(f).FoldRight([] , (m, acc) => m :: acc)
}

def res = F2(["a", "b"], x => [x + "x", x + "y"]);

Получаю естественно:
ax, ay
bx, by

Я так понимаю в Haskell-е каким-то образом на каждый элемент создается список и идет дальше, но я не понимаю как это происходит.
Сможете объяснить ?

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


_NN>-- | Evaluate each action in the sequence from left to right,
_NN>-- and collect the results.
_NN>sequence :: Monad m => [m a] -> m [a]
_NN>{-# INLINE sequence #-}
_NN>sequence ms = foldr k (return []) ms
_NN> where
_NN> k m m' = do { x <- m; xs <- m'; return (x:xs) }


_NN>Я так понимаю в Haskell-е каким-то образом на каждый элемент создается список и идет дальше, но я не понимаю как это происходит.
_NN>Сможете объяснить ?

Функция sequence делает эту работу, превращая список монад в монаду списка:

> :t sequence
sequence :: Monad m => [m a] -> m [a]
> sequence [Just 1, Just 3]
Just [1,3]
> sequence [[1,2], [10,20]]
[[1,10],[1,20],[2,10],[2,20]]

Во втором случае в качестве монады m берется список, то есть sequence получает тип [a]] -> [a]]. Но это не тождественное преобразование; можно отдельно поиграть с k из определения sequence, чтобы понять как оно работает:

> let k m m' = do { x <- m; xs <- m'; return (x:xs) }
> :t k
k :: Monad m => m a -> m [a] -> m [a]
> k [1,2] [[10,20],[100]]
[[1,10,20],[1,100],[2,10,20],[2,100]]

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

_NN>Я так понимаю в Haskell-е каким-то образом на каждый элемент создается список и идет дальше, но я не понимаю как это происходит.
_NN>Сможете объяснить ?

Код не очевиден, потому что завязан на монады, в частности, работает с монадой List (в Haskell список является монадой). В монаде List функция sequence возвращает декартово произведение списков. Если убрать монады, то код будет выглядеть так:

sequence xs = foldr f [[]] xs

-- Функция f - перемножение двух списков
f dim tails = concatMap (\e -> map (\tail -> e:tail) tails) dim 

-- или то же самое
-- f dim tails = [e:tail | e <- dim, tail <- tails]

На Nemerle вся нужная функция наверное будет выглядеть как-то так:

l.Map(f).FoldRight([[]], (m, acc) => m.Map(e => acc.Map(a => e:a)).Flatten())

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

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

_NN>>Я так понимаю в Haskell-е каким-то образом на каждый элемент создается список и идет дальше, но я не понимаю как это происходит.
_NN>>Сможете объяснить ?

Б>Код не очевиден, потому что завязан на монады, в частности, работает с монадой List (в Haskell список является монадой). В монаде List функция sequence возвращает декартово произведение списков. Если убрать монады, то код будет выглядеть так:
Список — монада , это я в курсе

Вот похоже где я промахнулся.
Я как-то не подумал об этом: (return []) == []]

Б>На Nemerle вся нужная функция наверное будет выглядеть как-то так:

Б>

Б>l.Map(f).FoldRight([[]], (m, acc) => m.Map(e => acc.Map(a => e::a)).Flatten())
Б>

Точно , она. (В Nemerle добавление к списку будет через "::" )

Всем спасибо.

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

D>Но ее реализация заточена под хаскельный ленивый рантайм и оптимизатор, в частности реализована через foldr, чтобы быть "хорошим консьюмером".
А как foldr получается ленивым ?
Ведь чтобы начать обход, нужно пройтись энергично по всему списку до конца.

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

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

D>>Но ее реализация заточена под хаскельный ленивый рантайм и оптимизатор, в частности реализована через foldr, чтобы быть "хорошим консьюмером".
_NN>А как foldr получается ленивым ?
_NN>Ведь чтобы начать обход, нужно пройтись энергично по всему списку до конца.

Кому нужно? Хаскелл же ленивый язык. Код foldr на каждом шаге рекурсии передает управление функции f:

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z []     = z 
foldr f z (x:xs) = f x (foldr f z xs)

Как только сворачивающая функция f перестает интересоваться своим вторым аргументом, foldr перестает интересоваться хвостом списка:

> foldr (\x y -> if x==10 then 0 else x+y) 0 [1..]
45

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

D>Кому нужно? Хаскелл же ленивый язык. Код foldr на каждом шаге рекурсии передает управление функции f:
Точно.

Аналогом в .NET будет что-то такое:

  FoldRightLazy[T, TOut](this seq : IEnumerable[T], acc : TOut, f : T * TOut -> TOut) : TOut
  {
    if (!seq.Any())
      acc
    else
      f(seq.First(), seq.Skip(1).FoldRightLazy(acc, f))
  }

Осталось разобраться еще с типами и можно будет сделать F ленивой как в Haskell-е .
Эх, не хватает более приятного синтаксиса для работы с IEnumerable.

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

_NN>Конкретно мне не нравится acc + [h'] , этот имеет линейную сложность.

На энергичных языках эффективнее будет прибавлять к началу, а потом одним махом перевернуть список.

-- допустим, у нас энергичный хаскелл (расставьте сами энергичные паттерны, или перепишите на ML)

for_fs_xs fs xs = reverse $ go' fs [] where
  go' []     accs = accs
  go' (f:ft) accs = go'' f ft xs accs
  ---
  go'' f ft []     accs = go' ft accs
  go'' f ft (x:xt) accs = go'' f ft xt ((f x):accs)

for_xs_fs fs xs = reverse $ go' xs [] where
  go' []     accs = accs
  go' (x:xt) accs = go'' x xt fs accs
  ---
  go'' x xt []     accs = go' xt accs
  go'' x xt (f:ft) accs = go'' x xt ft ((f x):accs)


for_fs_xs [f,g] [i,j] = [f i, f j, g i, g j]
for_xs_fs [f,g] [i,j] = [f i, g i, f j, g j]