Функция init

@allmass · Регистрация: 09.03.2019

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

В Prelude нашел два способа задания функции init:

Haskell
1
2
3
init [x] =  []
init (x:xs) =  x : init xs
init [] =  errorEmptyList "init"

Haskell
1
2
3
4
init [] =  errorEmptyList "init"
init (x:xs) =  init' x xs
  where init' _ [] = []
        init' y (z:zs) = y : init' z zs

Зачем нужен второй способ?

@Curry · 11.03.2019, 23:41

Второй вариант побыстрее, т.к. на каждом шаге выполняется только проверка на пустой список ([]), а в первом варианте и на список из одного элемента, и пустой. Второй вариант и используется (USE_REPORT_PRELUDE не определено). А первый оставлен для совместимости со стандартом
https://www.haskell.org/online... elude.html

@allmass · 12.03.2019, 00:21 **[ТС]**

А почему в первом случае проверка на пустой список выполняется на каждом шаге? Разве сопоставление с шаблонами не происходит сверху вниз?

@Curry · 12.03.2019, 02:09

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

Разве сопоставление с шаблонами не происходит сверху вниз?

Сверху вниз. Но компилятор проверяет на пустой список и в случае (x:xs). Чем меньше вариантов, тем быстрее.

@allmass · 12.03.2019, 02:39 **[ТС]**

Все равно не очень понятно почему во втором способе меньше вариантов. Можете объяснить подробнее или сказать где можно об этом почитать?

@Curry · 12.03.2019, 08:00

Попробуйте разобраться в промежуточном коде генерируемом компилятором.
Создаём файл Test.hs

Haskell
1
2
3
4
5
6
7
8
9
10
11
12
module Test where 
 
init1 :: [a] -> [a]
init1 [x] =  []
init1 (x:xs) =  x : init1 xs
init1 [] =  error "init1"
 
init2 :: [a] -> [a]
init2 [] =  error "init"
init2 (x:xs) =  init' x xs
  where init' _ [] = []
        init' y (z:zs) = y : init' z zs

Я использую stack и вызываю компилятор из него

Windows Batch file
1
stack exec ghc -- -O -ddump-simpl -dsuppress-all -fforce-recomp Test

Если вызывать на прямую

Windows Batch file
1
ghc -O -ddump-simpl -dsuppress-all -fforce-recomp Test

В выводе интересны фрагменты

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
-- RHS size: {terms: 4, types: 0, coercions: 0, joins: 0/0}     
$dIP3_r2bY                                                      
$dIP3_r2bY = PushCallStack $dIP1_r2bP $dIP2_r2bX EmptyCallStack 
                                                                
-- RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0}     
lvl_r2bZ                                                        
lvl_r2bZ = "init1"#                                             
                                                                
-- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0}     
lvl1_r2c0                                                       
lvl1_r2c0 = unpackCString# lvl_r2bZ                             
                                                                
-- RHS size: {terms: 4, types: 5, coercions: 4, joins: 0/0}     
lvl2_r2c1                                                       
lvl2_r2c1                                                       
  = \ @ a_a1WQ -> error ($dIP3_r2bY `cast` <Co:4>) lvl1_r2c0    
                                                                
Rec {                                                           
-- RHS size: {terms: 16, types: 18, coercions: 0, joins: 0/0}   
init1                                                           
init1                                                           
  = \ @ a_a1WQ ds_X28L ->                                       
      case ds_X28L of {                                         
        [] -> lvl2_r2c1;                                        
        : x_ap9 ds1_d28B ->                                     
          case ds1_d28B of wild1_X8 {                           
            [] -> [];                                           
            : ipv_s29k ipv1_s29l -> : x_ap9 (init1 wild1_X8)    
          }                                                     
      }                                                         
end Rec }

И

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
-- RHS size: {terms: 4, types: 0, coercions: 0, joins: 0/0}     
$dIP5_r2c5                                                      
$dIP5_r2c5 = PushCallStack $dIP1_r2bP $dIP4_r2c4 EmptyCallStack 
                                                                
-- RHS size: {terms: 1, types: 0, coercions: 0, joins: 0/0}     
lvl3_r2c6                                                       
lvl3_r2c6 = "init"#                                             
                                                                
-- RHS size: {terms: 2, types: 0, coercions: 0, joins: 0/0}     
lvl4_r2c7                                                       
lvl4_r2c7 = unpackCString# lvl3_r2c6                            
                                                                
-- RHS size: {terms: 4, types: 5, coercions: 4, joins: 0/0}     
init5                                                           
init5 = \ @ a_aTm -> error ($dIP5_r2c5 `cast` <Co:4>) lvl4_r2c7 
                                                                
Rec {                                                           
-- RHS size: {terms: 13, types: 13, coercions: 0, joins: 0/0}   
init4                                                           
init4                                                           
  = \ @ a_aTm ds_d28j ds1_d28k ->                               
      case ds1_d28k of {                                        
        [] -> [];                                               
        : z_aSY zs_aSZ -> : ds_d28j (init4 z_aSY zs_aSZ)        
      }                                                         
end Rec }                                                       
                                                                
-- RHS size: {terms: 10, types: 11, coercions: 0, joins: 0/0}   
init2                                                           
init2                                                           
  = \ @ a_aTm ds_X28t ->                                        
      case ds_X28t of {                                         
        [] -> init5;                                            
        : x_aSU xs_aSV -> init4 x_aSU xs_aSV                    
      }

@allmass · 12.03.2019, 23:33 **[ТС]**

К сожалению, я еще не настолько хорошо знаю язык, чтобы в этом разобраться. Если я правильно понял, это какой-то промежуточный язык? Может посоветуете где можно об этом почитать. В целом саму идею я вроде понял. В первом случае сначала идет проверка на список из одного элемента в 4 строке, а потом на непустой список в 5 строке, то есть проверяются два условия - сравнение со списком из одного элемента и сравнение с пустым списком. Во втором случае в 11 строке сначала идет проверка на пустой список, а потом в 12 строке на непустой список, то есть по сути проверяется одно и тоже условие - сравнение с пустым списком. Я правильно понял смысл?

@Curry · 13.03.2019, 00:01

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

Если я правильно понял, это какой-то промежуточный язык?

Да. Я об этом написал в начале прошлого сообщения.

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

Может посоветуете где можно об этом почитать.

Не знаю. Знаю как получить этот вариант вывода компилятора. Иногда полезно на него посмотреть что бы понять как работает код. Этот промежуточный код не сильно отличается от исходного, по этому разобраться можно.
Вложенные функции и даже некоторые выражения там вынесены в отдельные функции перед вызывающей их функцией.
Функции и операторы вызываются префиксно, то есть не z_aSY : zs_aSZ , а : z_aSY zs_aSZ .
init4 - это вложенная функция init' в исходнике. Она то и итерируется. Вот и сравните строки 21-30 первого фрагмента промежуточного кода со строками 20-25 второго фрагмента.

XRuZzz · 13.03.2019, 09:40

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

Если я правильно понял, это какой-то промежуточный язык?

Этот язык представляет из себя рассахаренный Haskell и называется Core.
Чисто по Core я доки не нашёл, видимо нужно читать про него в доке GHC и в спецификации Haskell:
GHC → 9.13.1.3. Core representation and simplification
Simon Marlow → Haskell 2010
Into the Core - Squeezing Haskell into Nine Constructors
A Supercompiler for Core Haskell
(если что, то я сам это мало изучал эти ссылки : )
Если хочется разобраться с Core, можно спросить в Haskell-сообществе, что почитать.

@allmass · 13.03.2019, 22:28 **[ТС]**

Если я правильно понял, то в первом случае шаблон сравнения с пустым списком и вывода ошибки будет проверяться первым, хотя и стоит в самом конце. Получается принцип сверху вниз в этом случае не действует, сначала проверяется последний шаблон ?

XRuZzz · 14.03.2019, 01:22

Хочется оставить ещё эту ссылку:
Учебник по Haskell → Реализация Haskell в GHC

Новые блоги и статьи Все статьи Все блоги /
сукцессия микоризы: основная теория в виде двух уравнений. 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 законам Кирхгофа и решает её. Последовательность действий:. . .

@Curry Модератор 5153 / 3465 / 536 Регистрация: 01.06.2013 Сообщений: 7,527 Записей в блоге: 9
	11.03.2019, 23:41
	Второй вариант побыстрее, т.к. на каждом шаге выполняется только проверка на пустой список ([]), а в первом варианте и на список из одного элемента, и пустой. Второй вариант и используется (USE_REPORT_PRELUDE не определено). А первый оставлен для совместимости со стандартом https://www.haskell.org/online... elude.html 1

@allmass 703 / 529 / 176 Регистрация: 09.03.2019 Сообщений: 1,404
	12.03.2019, 00:21 [ТС]
	А почему в первом случае проверка на пустой список выполняется на каждом шаге? Разве сопоставление с шаблонами не происходит сверху вниз? 0

@allmass 703 / 529 / 176 Регистрация: 09.03.2019 Сообщений: 1,404
	12.03.2019, 02:39 [ТС]
	Все равно не очень понятно почему во втором способе меньше вариантов. Можете объяснить подробнее или сказать где можно об этом почитать? 0

@allmass 703 / 529 / 176 Регистрация: 09.03.2019 Сообщений: 1,404
	12.03.2019, 23:33 [ТС]
	К сожалению, я еще не настолько хорошо знаю язык, чтобы в этом разобраться. Если я правильно понял, это какой-то промежуточный язык? Может посоветуете где можно об этом почитать. В целом саму идею я вроде понял. В первом случае сначала идет проверка на список из одного элемента в 4 строке, а потом на непустой список в 5 строке, то есть проверяются два условия - сравнение со списком из одного элемента и сравнение с пустым списком. Во втором случае в 11 строке сначала идет проверка на пустой список, а потом в 12 строке на непустой список, то есть по сути проверяется одно и тоже условие - сравнение с пустым списком. Я правильно понял смысл? 0

@allmass 703 / 529 / 176 Регистрация: 09.03.2019 Сообщений: 1,404
	13.03.2019, 22:28 [ТС]
	Если я правильно понял, то в первом случае шаблон сравнения с пустым списком и вывода ошибки будет проверяться первым, хотя и стоит в самом конце. Получается принцип сверху вниз в этом случае не действует, сначала проверяется последний шаблон ? 0

XRuZzz Антикодер 1888 / 870 / 48 Регистрация: 15.09.2012 Сообщений: 3,088
	14.03.2019, 01:22
	Хочется оставить ещё эту ссылку: Учебник по Haskell → Реализация Haskell в GHC 1