Здравствуйте, nikov, Вы писали:
N>В качестве тренировки написал такие функции (получение всех перестановок и всех подстрок строки):
Ну всё, nikov добрался и до Haskell'а. В GHC могут готовиться к тысячам баг репортов
Здравствуйте, nikov, Вы писали:
N>В качестве тренировки написал такие функции (получение всех перестановок и всех подстрок строки):
N>Как их можно переписать короче/элегантнее/понятнее/эффективнее? Конечно, не используя стандартных permutations и subsequences.
-- немного переделанный Ваш вариант
permutations [] = [[]]
permutations xs = [ x:ps | (ls,x:rs) <- map (flip splitAt $ xs) [0..length xs], ps <- permutations (ls ++ rs) ]
-------------------------------------------------------
-- вариант с разбиением списка
permutations1 [] = [ [] ]
permutations1 xs = [ x:ps | (ls,x,rs) <- splits xs, ps <- permutations1 (ls++rs) ]
-- для каждого элемента X в списке возвращает тупл вида
-- (элементы слева от X, элемент X, элементы справа от X)
-- splits [1..4] = [ ([],1,[2,3,4]), ([1],2,[3,4]), ([1,2],3,[4]), ([1,2,3],4,[]) ]
splits xss@(x:xs) = take (length xss) $ iterate next ([], x, xs)
where next (ls, x, r:rs) = (ls++[x], r, rs)
-------------------------------------------------------
-- вариант со сдвигом списка
permutations2 [] = [ [] ]
permutations2 xs = [ y:ps | (y:ys) <- shifts xs, ps <- permutations1 ys ]
-- все варианты циклического сдвига списка
-- shifts [1..4] = [ [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3] ]
shifts xs = take (length xs) $ iterate shift xs
where shift (x:xs) = xs ++ [x]
-------------------------------------------------------
-- еще вариант (на сочетании голов и хвостов списка)
permutations3 [] = [ [] ]
permutations3 xs = [ r:ps | (ls, r:rs) <- zip (inits xs) (tails xs), ps <- permutations3 (ls++rs) ]
Все варианты приблизительно равны по скорости и памяти, за исключением последнего, который отличается в худшую стороны раза в полтора
N>[/haskell]
N>subsequences :: [a] -> [a]]
N>subsequences = ([]
.(concatMap (tail.inits)).tails
N>[/haskell]
Здесь и так все красиво. Лучше и не придумаешь. Правда, я не очень люблю функции без параметров. На мой взгляд их удобно использовать в больших выражения, но не сами по себе. Поэтому, я бы переписал с явным указанием параметров.
[/haskell]
subsequences xs = [] : (concatMap (tail.inits) $ tails xs)
[/haskell]
В качестве тренировки написал такие функции (получение всех перестановок и всех подстрок строки):
permutations :: [a] -> [[a]]
permutations [] = [[]]
permutations xs = [x:p | (x,n) <- zip xs [0..], p <- let (l,r) = splitAt n xs in permutations $ l ++ tail r]
subsequences :: [a] -> [[a]]
subsequences = ([]:).(concatMap (tail.inits)).tails
Как их можно переписать короче/элегантнее/понятнее/эффективнее? Конечно, не используя стандартных permutations и subsequences.
Здравствуйте, nikov, Вы писали:
N>В качестве тренировки написал такие функции (получение всех перестановок и всех подстрок строки):
N>N>permutations :: [a] -> [[a]]
N>permutations [] = [[]]
N>permutations xs = [x:p | (x,n) <- zip xs [0..], p <- let (l,r) = splitAt n xs in permutations $ l ++ tail r]
N>
N>Как их можно переписать короче/элегантнее/понятнее/эффективнее? Конечно, не используя стандартных permutations и subsequences.
Перестановки в соседнем топике были
http://rsdn.ru/forum/message/3386768.1.aspxАвтор: Буравчик
Дата: 12.05.09
.
Здравствуйте, achmed, Вы писали:
A>Перестановки в соседнем топике были http://rsdn.ru/forum/message/3386768.1.aspxАвтор: Буравчик
Дата: 12.05.09
.
Там не очень хорошее решение — оно требует Eq a.
Здравствуйте, nikov, Вы писали:
N>N>subsequences :: [a] -> [[a]]
N>subsequences = ([]:).(concatMap (tail.inits)).tails
N>
Я тут сообразил, что этот код делает не то, что стандартная subsequences — он выдает только непрерывные подпоследовательности.
Попробовал это исправить так:
subsequences [] = [[]]
subsequences (x:xs) = s ++ map (x:) s where s = subsequences xs
Но, увы, в отличие от стандартной функции, этот код не работает с бесконечными последовательностями. Попыхтев, написал такой вариант:
subsequences xs = concat f
where f = [[]]:[map (++[x]) $ concat $ take (n+1) f | (n,x) <- zip [0..] xs]
Он работает, как требуется, но выглядит уже не очень элегатно. Заглянул в стандартную реализацию — она покрасивее, нет явной работы с индексами, но идею уловить пока не смог. Прошу объяснить или предложить свой понятный вариант.
Здравствуйте, nikov, Вы писали:
N>Он работает, как требуется, но выглядит уже не очень элегатно. Заглянул в стандартную реализацию — она покрасивее, нет явной работы с индексами, но идею уловить пока не смог. Прошу объяснить или предложить свой понятный вариант.
nonEmptySubsequences :: [a] -> [[a]]
nonEmptySubsequences [] = []
nonEmptySubsequences (x:xs) = [x] : foldr f [] (nonEmptySubsequences xs)
where f ys r = ys : (x : ys) : r
Всё просто. Все подпоследовательности берутся как:
1. Первый элемент списка ([x])
2. Все подпоследовательности хвоста (nonEmptySubsequences xs -> ys)
3. Все подпоследовательности хвоста с присобаченной головой (nonEmptySubsequences xs -> x : ys)
foldr тут просто берёт все подпоследовательности хвоста и к каждому второму элементу приставляет голову, т.е. это тот же вариант, что и у тебя с двумя map'ами, только map сначала возвращает всю подпоследовательность без головы (а если это бесконечный список, то он не угомонится), а только потом сзади ставится подпоследовательность с головой.
Здравствуйте, nikov, Вы писали:
NN>Он работает, как требуется, но выглядит уже не очень элегатно. Заглянул в стандартную реализацию — она покрасивее, нет явной работы с индексами, но идею уловить пока не смог. Прошу объяснить или предложить свой понятный вариант.
Возможно (но не факт), проще понять будет так:
nonEmptySeq [] = []
nonEmptySeq (x:xs) = [x] : (concat $ zipWith (\a b -> [a,b]) xss (map (x:) xss) where xss = nonEmptySeq xs
