Здравствуйте, _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 вся нужная функция наверное будет выглядеть как-то так:
Здравствуйте, _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>-- | 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>Здравствуйте, 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
Подскажите как сделать оптимальнее и возможно правильнее.
Имеем список ,скажем , строк и функцию принимающую строку и возвращающую список строк.
На каждый элемент списка получаем список из функции и нужно его обойти и передать хвост дальше.
Скажем при данных "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, byforeach(r in res)
WriteLine($"..$r");
_ = ReadLine();
}
}
Здравствуйте, _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"])
Здравствуйте, 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>>Я так понимаю в Haskell-е каким-то образом на каждый элемент создается список и идет дальше, но я не понимаю как это происходит. _NN>>Сможете объяснить ?
Б>Код не очевиден, потому что завязан на монады, в частности, работает с монадой List (в Haskell список является монадой). В монаде List функция sequence возвращает декартово произведение списков. Если убрать монады, то код будет выглядеть так:
Список — монада , это я в курсе
Вот похоже где я промахнулся.
Я как-то не подумал об этом: (return []) == []]
Б>На Nemerle вся нужная функция наверное будет выглядеть как-то так:
Б>
Здравствуйте, deniok, Вы писали:
D>Но ее реализация заточена под хаскельный ленивый рантайм и оптимизатор, в частности реализована через foldr, чтобы быть "хорошим консьюмером".
А как foldr получается ленивым ?
Ведь чтобы начать обход, нужно пройтись энергично по всему списку до конца.
Здравствуйте, 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]