Максимальное количество идущих подряд списков

@Oldi · Регистрация: 19.11.2012

Студворк — интернет-сервис помощи студентам

Привет. Помогите решить задачу. Условие: Для заданного списка определить максимальное количество идущих подряд списков.

@Catstail · 19.11.2012, 16:24

Может, максимальное количество одинаковых элементов, идущих подряд?

@Oldi · 19.11.2012, 16:33 **[ТС]**

Нет. Вот имеется список, некоторые элементы которого являются списками.. К примеру [1,2,[3,4],[5,6],7,8,[1,2],[3,4],[5,5],4] - в списке максимальное последовательность списков равна трём. Вот логику сам ход решения задачи я понимаю, но не внимаю вообще как реализовать на haskell. Как проверить является ли элемент списка списком?

@Catstail · 19.11.2012, 16:41

Поиск максимальной цепочки одинаковых:

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
-- Вспомогательная функция
 
maxEq :: (Eq a) => [a] -> Int -> Int -> Int
maxEq [] _ ma = ma
maxEq [y] te ma = if (te > ma) then te else ma
maxEq (x:xs) te ma = if (x == (head xs)) then maxEq xs (te+1) ma
                        else if (te > ma) then maxEq xs 1 te
                                          else maxEq xs 1 ma
 
-- Собственно решение
   
maxLenEq :: (Eq a) => [a] -> Int
maxLenEq x = maxEq x 1 0
 
-- Проверка:
 
Main> maxLenEq [1,2,1,1,1,2,2,3,2,2,2,2,2,3]
5

А вот создать список вида: [1,2,[3,4],[5,6],7,8,[1,2],[3,4],[5,5],4] в Haskell, по-моему, нельзя...

@Сtrl · 19.11.2012, 16:43

Сообщение от Oldi

К примеру [1,2,[3,4],[5,6],7,8,[1,2],[3,4],[5,5],4]

Так не может быть, т. к. список хранит в себе элементы одного типа. Либо одиночные элементы представляются в виде списка из одного элемента (считаются ли тогда пустые списки списками?), либо надо использовать структуру данных вроде такой:

Haskell
1
data Elem a = SingleElem a | MultiElem [a]

@Oldi · 19.11.2012, 16:53 **[ТС]**

да, точно. Спасибо вам Catstail и Сtrl

@Сtrl · 19.11.2012, 16:55

Таки да, но если этот список содержит списки, то он уже не может содержать одиночные элементы как таковые - тип данных другой.

Haskell
1
2
3
4
5
6
-- Можно
[1,2,3]
[[1],[2,3]]
 
-- Нельзя
[1,[2,3]]

@Oldi · 19.11.2012, 20:38 **[ТС]**

да я упустил этот момент... там список исключительно из списков.. Ну значит с правильностью условия задания можно поспорить..

Добавлено через 3 часа 39 минут
Был сегодня на паре, показывал наработки этого задания. Преподаватель сказал что такая запись в haskell - [1,2,[3,4],[5,6],7,8,[1,2],[3,4],[5,5],4], имеет смысл. Потом я пробовал показать ей несколько примеров, что-то типа:

Haskell
1
funk x = head x.

--ввожу
funk [[1,2],3,[3,4]]

--результат
ошибка

--ввожу
funk [[1,2],[3],[3,4]]

--результат
[1,2]

возможно я что-нибудь в коде пропустил, например типизацию. Но этот пример подтвердил ваши слова.

@Oldi · 25.11.2012, 13:56 **[ТС]**

CAtstail я переделывал Вашу задачу, свёл к условию - найти максимальное кол-во подряд идущих нулей. И тут проблема в типах.

Вот смотрите.. строка

Haskell
1
maxEq :: (Eq a) => [a] -> Int -> Int -> Int -> Int

означает что в функцию maxEq будет передан список любого типа и 3 переменные типа Int, и на выходе мы получим число типа Int. Так да?

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
maxEq :: (Eq a) => [a] -> Int -> Int -> Int -> Int
maxEq [] _ ma zer = ma
maxEq [y] te ma zer = if (te > ma) then te else ma
maxEq (x:xs) te ma zer =
                        if (x == zer) 
                            then maxEq xs (te+1) ma zer
                            else if (te > ma) 
                                    then maxEq xs 1 te zer
                                    else maxEq xs 1 ma zer
 
-- Собственно решение
   
maxLenEq :: (Eq a) => [a] -> Int 
maxLenEq x = maxEq x 1 0 0

Ошибка вот какая:

Code
1
2
3
4
ERROR file:.\haskell.hs:2 - Inferred type is not general enough
*** Expression    : maxEq
*** Expected type : Eq a => [a] -> Int -> Int -> Int -> Int
*** Inferred type : Eq Int => [Int] -> Int -> Int -> Int -> Int

@Nameless One · 27.11.2012, 02:44

Сообщение от Oldi

означает что в функцию maxEq будет передан список любого типа и 3 переменные типа Int

Вот тут уже логическая ошибка. Функция принимает список элементов любого типа, но потом сравнивает элемент этого типа со значением типа Int. Т.е. сравниваются два значения с типами (Eq a) => a и Int, что неверно, т.к. оператор сравнения определен только для одинаковых типов. Так что я бы изменил сигнатуру функции так:

Haskell
1
[Int] -> Int -> Int -> Int -> Int

Или для более общего случая:

Haskell
1
(Eq a, Integral a) => [a] -> a -> a -> a -> a

Но я бы решал задачу с помощью функции group:

Haskell
1
2
3
4
iimport Data.List
 
maxLenOfSuccZeros :: (Eq a, Num a) => [a] -> Int
maxLenOfSuccZeros = maximum . (0 :) . map length . filter ((== 0) . head) . group

Идея такая: используем функцию group, чтобы разбить список на группы последовательно идущих одинаковых элементов, затем отфильтровываем (filter) все группы, кроме состоящих из нулей, затем находим длину каждой группы (map length), (UPD: добавляем ноль на случай, если получился пустой список, т.е. на случай, если нет ни одной группы с нулями), потом с помощью функции maximum находим максимальную длину.

UPD: Поправил на случай, если в списке нет нулей.

@Oldi · 28.11.2012, 15:06 **[ТС]**

Nameless One, спасибо. С фильтром очень интересно и лаконично получается. Вот как Вы, Nameless One, считаете, можно ли в haskell-е передать список, элементы которого могут быть как и списками так и другими типами( Int, Char и т.д.) . [1,[2,3],'a]. Кортежем можно, но в условии у меня именно список.

@Nameless One · 28.11.2012, 16:02

Oldi, списки в Haskell гомогенные, т.е. хранят элементы одного типа. Это, собственно, видно из сигнатуры типа. Существуют разные способы обхода такой ситуации, вариант с ADT уже был предложен выше. Вот другие:

Используя специальный тип-wrapper Dynamic:

Haskell
1
2
3
4
5
6
7
import Data.Dynamic
 
hetList :: [Dynamic]
hetList = [ toDyn (1 :: Int)
          , toDyn ([2, 3] :: [Int])
          , toDyn 'a'
          ]

Haskell
1
2
3
4
5
> hetList
[<<Int>>,<<[Int]>>,<<Char>>]
> fromDynamic (hetList !! 1) :: Maybe [Int]
Just [2,3]
>

Используя экзистенциальные типы. С их использованием решение задачи из поста #3 выглядит следующим образом (также пример с символами и строками):

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
{-# LANGUAGE ExistentialQuantification #-}
 
import Data.List
 
class ListOrAtom a where
    isList :: a -> Bool
 
instance ListOrAtom Int where
    isList = const False
 
instance ListOrAtom a => ListOrAtom [a] where
    isList = const True
 
data ListItem = forall a. ListOrAtom a => MkItem a
 
pack :: ListOrAtom a => a -> ListItem
pack = MkItem
 
hlist ::[ListItem]
hlist = [ pack (1 :: Int)
        , pack (2 :: Int)
        , pack ([3,4] :: [Int])
        , pack ([5,6] :: [Int])
        , pack (7 :: Int)
        , pack (8 :: Int)
        , pack ([1,2] :: [Int])
        , pack ([3,4] :: [Int])
        , pack ([5,5] :: [Int])
        , pack (4 :: Int)
        ]
 
instance ListOrAtom Char where
    isList = const False
 
hlistWithChars ::[ListItem]
hlistWithChars = [ pack (1 :: Int)
                 , pack "foo"
                 , pack 'c'
                 , pack ([1,2,3] :: [Int])
                 , pack "bar"
                 , pack 'q'
                 ]
 
maxNumOfSuccLists ::[ListItem] -> Int
maxNumOfSuccLists = maximum . (0 :) . map length . filter head . group . map f
    where f (MkItem a) = isList a

Haskell
1
2
3
4
5
> maxNumOfSuccLists hlist
3
> maxNumOfSuccLists hlistWithChars
2
>

Есть пакет HList («strongly typed heterogenous lists» и не только). Вот статья от автора с описанием, в ней также рассмотрены и другие существующие подходы.

Подробнее см. http://www.haskell.org/haskell... ollections.

@Oldi · 28.11.2012, 22:04 **[ТС]**

Вот что требовалось изначально, спасибо! Суть в чём.. создали собственный тип, определяем с помощью дополнительных функций типы элементов, фильтруем слаживаем по группам и находим максимальную группу.
Если подробнее: Создаём класс, в котором есть функция isList принимающая элемент любого типа - возвращающая истину или ложь.

Haskell
1
2
class ListOrAtom a where
isList :: a -> Bool

Затем инстансируем функции, Int является экземпляром ListOrAtom, либо если элемент пришедший на вход функции будет типа Int, то будет возвращено значение Ложь:

Haskell
1
2
instance ListOrAtom Int where
isList = const False

Если придёт списо, то возвратит функция Истино:

Haskell
1
2
instance ListOrAtom a => ListOrAtom [a] where
isList = const True

Дальше создаём свой тип данных... вот здесь проблемка небольшая ... Я не нашёл описания forall, это что-то своё или какой-то оператор?

Ну судя по всему далече происходит так... Функцией pack мы задаём элементы списка...Функция определяет типы элементов, возвращает True или False, после чего у нас будет список из True либо False.

В итоге получившийся список мы разбиваем на группы, отфильтрованные по значению True и взят максимум из длин этих групп. Вот чтобы вы меня направили ещё на путь что такое forall и MkItem. Спасибо большое!

@Nameless One · 29.11.2012, 06:25

Сообщение от Oldi

Int является экземпляром ListOrAtom, либо если элемент пришедший на вход функции будет типа Int, то будет возвращено значение Ложь:

Верно, но почему "либо"?

Сообщение от Oldi

Функцией pack мы задаём элементы списка

Если точнее, то функция pack запаковывает (оборачивает) значения любого типа, являющегося экземпляром класса ListOrAtom, в значение типа ListItem. Результирующий список hlist остается гомогенным (опять видно из сигнатуры[ListItem]), т.е. хранит значения одного типа - ListItem, который, в свою очередь, является "контейнером" для значений различных типов.

Здесь функция pack является просто синонимом конструктора MkItem типа ListItem, введенной для удобства. Можно вместо нее использовать конструктор MkItem.

Сообщение от Oldi

Вот чтобы вы меня направили ещё на путь что такое forall и MkItem.

MkItem - это всего-навсего конструктор типа ListItem, т.е. функция, принимающая любой тип, являющийся экземпляром ListOrAtom, и возвращающая значение типа ListItem.

Это расширение языка, которое вводит ключевое слово "forall", позволяющее указывать явную квантификацию (см. [1] - статья в wikibooks) для сигнатуры типа вместо неявной (универсальной), которая по умолчанию используется в Haskell. Это позволяет нам использовать т.н. "экзистенциальные типы" (см. [2] - отличная статья в "Практике функционального программирования"), чтобы обойти ограничение системы типов Haskell 98, которое требует того, чтобы типы, используемые при подстановке вместо типовых переменных, были мономорфными.

Запись вида

Haskell
1
data ListItem = forall a . ListOrAtom a => MkItem a

следует читать так: "тип ListItem для любого типа a, являющегося экземпляром класса ListOrAtom, определяет конструктор MkItem с сигнатурой (ListOrAtom a) => a -> ListItem".

Экзистенциальный тип данных можно так же определить с использованием GADT's (Generalized Algebraic Datatypes, см. [3] и [4]):

Haskell
1
2
data ListItem where
  MkItem :: ListOrAtom a => a -> ListItem

Для использования GADTs в Haskell нужно включить соответствующее расширение в начале файла с исходным кодом:

Haskell
1
{-# LANGUAGE GADTs #-}

Ссылки:

[1]: http://en.wikibooks.org/wiki/H... fied_types
[2]: http://fprog.ru/2010/issue4/ro... stentials/
[3]: http://en.wikibooks.org/wiki/Haskell/GADT
[4]: http://www.haskell.org/haskell... or_dummies

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .	Почему дизайн решает? Neotwalker 09.01.2026 В современном мире, где конкуренция за внимание потребителя достигла пика, дизайн становится мощным инструментом для успеха бренда. Это не просто красивый внешний вид продукта или сайта — это. . .
Модель микоризы: классовый агентный подход 3 anaschu 06.01.2026 aa0a7f55b50dd51c5ec569d2d10c54f6/ O1rJuneU_ls https:/ / vkvideo. ru/ video-115721503_456239114	Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ФедосеевПавел 06.01.2026 Owen Logic: О недопустимости использования связки «аналоговый ПИД» + RegKZR ВВЕДЕНИЕ Введу сокращения: аналоговый ПИД — ПИД регулятор с управляющим выходом в виде числа в диапазоне от 0% до. . .	Модель микоризы: классовый агентный подход 2 anaschu 06.01.2026 репозиторий https:/ / github. com/ shumilovas/ fungi ветка по-частям. коммит Create переделка под биомассу. txt вход sc, но sm считается внутри мицелия. кстати, обьем тоже должен там считаться. . . .	Расчёт токов в цепи постоянного тока igorrr37 05.01.2026 / * Дана цепь постоянного тока с сопротивлениями и источниками (напряжения, ЭДС и тока). Найти токи и напряжения во всех элементах. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа и. . .

@Oldi 0 / 0 / 0 Регистрация: 19.11.2012 Сообщений: 19

	Максимальное количество идущих подряд списков 19.11.2012, 14:46. Показов 2915. Ответов 13 Метки нет (Все метки) Привет. Помогите решить задачу. Условие: Для заданного списка определить максимальное количество идущих подряд списков. 0

@Catstail Супер-модератор 38167 / 21102 / 4307 Регистрация: 12.02.2012 Сообщений: 34,690 Записей в блоге: 14
	19.11.2012, 16:24
	Может, максимальное количество одинаковых элементов, идущих подряд? 1

@Oldi 0 / 0 / 0 Регистрация: 19.11.2012 Сообщений: 19
	19.11.2012, 16:33 [ТС]
	Нет. Вот имеется список, некоторые элементы которого являются списками.. К примеру [1,2,[3,4],[5,6],7,8,[1,2],[3,4],[5,5],4] - в списке максимальное последовательность списков равна трём. Вот логику сам ход решения задачи я понимаю, но не внимаю вообще как реализовать на haskell. Как проверить является ли элемент списка списком? 0

@Oldi 0 / 0 / 0 Регистрация: 19.11.2012 Сообщений: 19
	19.11.2012, 16:53 [ТС]
	да, точно. Спасибо вам Catstail и Сtrl 0

@Oldi 0 / 0 / 0 Регистрация: 19.11.2012 Сообщений: 19
	28.11.2012, 15:06 [ТС]
	Nameless One, спасибо. С фильтром очень интересно и лаконично получается. Вот как Вы, Nameless One, считаете, можно ли в haskell-е передать список, элементы которого могут быть как и списками так и другими типами( Int, Char и т.д.) . [1,[2,3],'a]. Кортежем можно, но в условии у меня именно список. 0