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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
1093
1094
1095
1096
1097
1098
1099
1100
1101
1102
1103
1104
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
1279
1280
1281
1282
1283
1284
1285
1286
1287
1288
1289
1290
1291
1292
1293
1294
1295
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328
1329
1330
1331
1332
1333
1334
1335
1336
1337
1338
1339
1340
1341
1342
1343
1344
1345
1346
1347
1348
1349
1350
1351
1352
1353
1354
1355
1356
1357
1358
1359
1360
1361
1362
1363
1364
1365
1366
1367
1368
1369
1370
1371
1372
1373
1374
1375
1376
1377
1378
1379
1380
1381
1382
1383
1384
1385
1386
1387
1388
1389
1390
1391
1392
1393
1394
1395
1396
1397
1398
1399
1400
1401
1402
1403
1404
1405
1406
1407
1408
1409
1410
1411
1412
1413
1414
1415
1416
1417
1418
1419
1420
1421
1422
1423
1424
1425
1426
1427
1428
1429
1430
1431
1432
1433
1434
1435
1436
1437
1438
1439
1440
1441
1442
1443
1444
1445
1446
1447
1448
1449
1450
1451
1452
1453
1454
1455
1456
1457
1458
1459
1460
1461
1462
1463
1464
1465
1466
1467
1468
1469
1470
1471
1472
1473
1474
1475
1476
1477
1478
1479
1480
1481
1482
1483
1484
1485
1486
1487
1488
1489
1490
1491
1492
1493
1494
1495
1496
1497
1498
1499
1500
1501
1502
1503
1504
1505
1506
1507
1508
1509
1510
1511
1512
1513
1514
1515
1516
1517
1518
1519
1520
1521
1522
1523
1524
1525
1526
1527
1528
1529
1530
1531
1532
1533
1534
1535
1536
1537
1538
1539
1540
1541
1542
1543
1544
1545
1546
1547
1548
1549
1550
1551
1552
1553
1554
1555
1556
1557
1558
1559
1560
1561
1562
1563
1564
1565
1566
1567
1568
1569
1570
1571
1572
1573
1574
1575
1576
1577
1578
1579
1580
1581
1582
1583
1584
1585
1586
1587
1588
1589
1590
1591
1592
1593
1594
1595
1596
1597
1598
1599
1600
1601
1602
1603
1604
1605
1606
1607
1608
1609
1610
1611
1612
1613
1614
1615
1616
1617
1618
1619
1620
1621
1622
1623
1624
1625
1626
1627
1628
1629
1630
1631
1632
1633
1634
1635
1636
1637
1638
1639
1640
1641
1642
1643
1644
1645
1646
1647
1648
1649
1650
1651
1652
1653
1654
1655
1656
1657
1658
1659
1660
1661
1662
1663
1664
1665
1666
1667
1668
1669
1670
1671
1672
1673
1674
1675
1676
1677
1678
1679
1680
1681
1682
1683
1684
1685
1686
1687
1688
1689
1690
1691
1692
1693
1694
1695
1696
1697
1698
1699
1700
1701
1702
1703
1704
1705
1706
1707
1708
1709
1710
1711
1712
1713
1714
1715
1716
1717
1718
1719
1720
1721
1722
1723
1724
1725
1726
1727
1728
1729
1730
1731
1732
1733
1734
1735
1736
1737
1738
1739
1740
1741
1742
1743
1744
1745
1746
1747
1748
1749
1750
1751
1752
1753
1754
1755
1756
1757
1758
1759
1760
1761
1762
1763
1764
1765
1766
1767
1768
1769
1770
1771
1772
1773
1774
1775
1776
1777
1778
1779
1780
1781
1782
1783
1784
1785
1786
1787
1788
1789
1790
1791
1792
1793
1794
1795
1796
1797
1798
1799
1800
1801
1802
1803
1804
1805
1806
1807
1808
1809
1810
1811
1812
1813
1814
1815
1816
1817
1818
1819
1820
1821
1822
1823
1824
1825
1826
1827
1828
1829
1830
1831
1832
1833
1834
1835
1836
1837
1838
1839
1840
1841
1842
1843
1844
1845
1846
1847
1848
1849
1850
1851
1852
1853
1854
1855
1856
1857
1858
1859
1860
1861
1862
1863
1864
1865
1866
1867
1868
1869
1870
1871
1872
1873
1874
1875
1876
1877
1878
1879
1880
1881
1882
1883
1884
1885
1886
1887
1888
1889
1890
1891
1892
1893
1894
1895
1896
1897
1898
1899
1900
1901
1902
1903
1904
1905
1906
1907
1908
1909
1910
1911
1912
1913
1914
1915
1916
1917
1918
1919
1920
1921
1922
1923
1924
1925
1926
1927
1928
1929
1930
1931
1932
1933
1934
1935
1936
1937
1938
1939
1940
1941
1942
1943
1944
1945
1946
1947
1948
1949
1950
1951
1952
1953
1954
1955
1956
1957
1958
1959
1960
1961
1962
1963
1964
1965
1966
1967
1968
1969
1970
1971
1972
1973
1974
1975
1976
1977
1978
1979
1980
1981
1982
1983
1984
1985
1986
1987
1988
1989
1990
1991
1992
1993
1994
1995
1996
1997
1998
1999
2000
2001
2002
2003
2004
2005
2006
2007
2008
2009
2010
2011
2012
2013
2014
2015
2016
2017
2018
2019
2020
2021
2022
2023
2024
2025
2026
2027
2028
2029
2030
2031
2032
2033
2034
2035
2036
2037
2038
2039
2040
2041
2042
2043
2044
2045
2046
2047
2048
2049
2050
2051
2052
2053
2054
2055
2056
2057
2058
2059
2060
2061
2062
2063
2064
2065
2066
2067
2068
2069
2070
2071
2072
2073
2074
2075
2076
2077
2078
2079
2080
2081
2082
2083
2084
2085
2086
2087
2088
2089
2090
2091
2092
2093
2094
2095
2096
2097
2098
2099
2100
2101
2102
2103
2104
2105
2106
2107
2108
2109
2110
2111
2112
2113
2114
2115
2116
2117
2118
2119
2120
2121
2122
2123
2124
2125
2126
2127
2128
2129
2130
2131
2132
2133
2134
2135
2136
2137
2138
2139
2140
2141
2142
2143
2144
2145
2146
2147
2148
2149
2150
2151
2152
2153
2154
2155
2156
2157
2158
2159
2160
2161
2162
2163
2164
2165
2166
2167
2168
2169
2170
2171
2172
2173
2174
2175
2176
2177
2178
2179
2180
2181
2182
2183
2184
2185
2186
2187
2188
2189
2190
2191
2192
2193
2194
2195
2196
2197
2198
2199
2200
2201
2202
2203
2204
2205
2206
2207
2208
2209
2210
2211
2212
2213
2214
2215
2216
2217
2218
2219
2220
2221
2222
2223
2224
2225
2226
2227
2228
2229
2230
2231
2232
2233
2234
2235
2236
2237
2238
2239
2240
2241
2242
2243
2244
2245
2246
2247
2248
2249
2250
2251
2252
2253
2254
2255
2256
2257
2258
2259
2260
2261
2262
2263
2264
2265
2266
2267
2268
2269
2270
2271
2272
2273
2274
2275
2276
2277
2278
2279
2280
2281
2282
2283
2284
2285
2286
2287
2288
2289
2290
2291
2292
2293
2294
2295
2296
2297
2298
2299
2300
2301
2302
2303
2304
2305
2306
2307
2308
2309
2310
2311
2312
2313
2314
2315
2316
2317
2318
2319
2320
2321
2322
2323
2324
2325
2326
2327
2328
2329
2330
2331
2332
2333
2334
2335
2336
2337
2338
2339
2340
2341
2342
2343
2344
2345
2346
2347
2348
2349
2350
2351
2352
2353
2354
2355
2356
2357
2358
2359
2360
2361
2362
2363
2364
2365
2366
2367
2368
2369
2370
2371
2372
2373
2374
2375
2376
2377
2378
|
{-# LANGUAGE DeriveFoldable #-}
{-# LANGUAGE FlexibleInstances #-}
{-# LANGUAGE NoImplicitPrelude #-}
{-# LANGUAGE ScopedTypeVariables #-}
{-# LANGUAGE StandaloneDeriving #-}
{-# LANGUAGE Trustworthy #-}
{-# LANGUAGE TypeOperators #-}
-----------------------------------------------------------------------------
-- |
-- Module : Data.Foldable
-- Copyright : Ross Paterson 2005
-- License : BSD-style (see the LICENSE file in the distribution)
--
-- Maintainer : libraries@haskell.org
-- Stability : experimental
-- Portability : portable
--
-- Class of data structures that can be folded to a summary value.
--
-----------------------------------------------------------------------------
module Data.Foldable (
Foldable(..),
-- * Special biased folds
foldrM,
foldlM,
-- * Folding actions
-- ** Applicative actions
traverse_,
for_,
sequenceA_,
asum,
-- ** Monadic actions
mapM_,
forM_,
sequence_,
msum,
-- * Specialized folds
concat,
concatMap,
and,
or,
any,
all,
maximumBy,
minimumBy,
-- * Searches
notElem,
find
-- * Overview
-- $overview
-- ** Chirality
-- $chirality
-- ** Recursive and corecursive reduction
-- $reduction
-- *** Strict recursive folds
-- $strict
-- **** List of strict functions
-- $strictlist
-- *** Lazy corecursive folds
-- $lazy
-- **** List of lazy functions
-- $lazylist
-- *** Short-circuit folds
-- $shortcircuit
-- **** List of short-circuit functions
-- $shortlist
-- *** Hybrid folds
-- $hybrid
-- ** Generative Recursion
-- $generative
-- ** Avoiding multi-pass folds
-- $multipass
-- * Defining instances
-- $instances
-- *** Being strict by being lazy
-- $strictlazy
-- * Laws
-- $laws
-- * Notes
-- $notes
-- * See also
-- $also
) where
import Data.Bool
import Data.Either
import Data.Eq
import Data.Functor.Utils (Max(..), Min(..), (#.))
import qualified GHC.List as List
import Data.Maybe
import Data.Monoid
import Data.Ord
import Data.Proxy
import GHC.Arr ( Array(..), elems, numElements,
foldlElems, foldrElems,
foldlElems', foldrElems',
foldl1Elems, foldr1Elems)
import GHC.Base hiding ( foldr )
import GHC.Generics
import GHC.Tuple (Solo (..))
import GHC.Num ( Num(..) )
-- $setup
-- >>> :set -XDeriveFoldable
-- >>> import Prelude
-- >>> import Data.Monoid (Product (..), Sum (..))
-- >>> data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a) deriving (Show, Foldable)
infix 4 `elem`, `notElem`
-- XXX: Missing haddock feature. Links to anchors in other modules
-- don't have a sensible way to name the link within the module itself.
-- Thus, the below "Data.Foldable#overview" works well when shown as
-- @Data.Foldable@ from other modules, but in the home module it should
-- be possible to specify alternative link text. :-(
-- | The Foldable class represents data structures that can be reduced to a
-- summary value one element at a time. Strict left-associative folds are a
-- good fit for space-efficient reduction, while lazy right-associative folds
-- are a good fit for corecursive iteration, or for folds that short-circuit
-- after processing an initial subsequence of the structure's elements.
--
-- Instances can be derived automatically by enabling the @DeriveFoldable@
-- extension. For example, a derived instance for a binary tree might be:
--
-- > {-# LANGUAGE DeriveFoldable #-}
-- > data Tree a = Empty
-- > | Leaf a
-- > | Node (Tree a) a (Tree a)
-- > deriving Foldable
--
-- A more detailed description can be found in the overview section of
-- "Data.Foldable#overview".
--
class Foldable t where
{-# MINIMAL foldMap | foldr #-}
-- | Given a structure with elements whose type is a 'Monoid', combine them
-- via the monoid's @('<>')@ operator. This fold is right-associative and
-- lazy in the accumulator. When you need a strict left-associative fold,
-- use 'foldMap'' instead, with 'id' as the map.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> fold [[1, 2, 3], [4, 5], [6], []]
-- [1,2,3,4,5,6]
--
-- >>> fold $ Node (Leaf (Sum 1)) (Sum 3) (Leaf (Sum 5))
-- Sum {getSum = 9}
--
-- Folds of unbounded structures do not terminate when the monoid's
-- @('<>')@ operator is strict:
--
-- >>> fold (repeat Nothing)
-- * Hangs forever *
--
-- Lazy corecursive folds of unbounded structures are fine:
--
-- >>> take 12 $ fold $ map (\i -> [i..i+2]) [0..]
-- [0,1,2,1,2,3,2,3,4,3,4,5]
-- >>> sum $ take 4000000 $ fold $ map (\i -> [i..i+2]) [0..]
-- 2666668666666
--
fold :: Monoid m => t m -> m
fold = foldMap id
-- | Map each element of the structure into a monoid, and combine the
-- results with @('<>')@. This fold is right-associative and lazy in the
-- accumulator. For strict left-associative folds consider 'foldMap''
-- instead.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> foldMap Sum [1, 3, 5]
-- Sum {getSum = 9}
--
-- >>> foldMap Product [1, 3, 5]
-- Product {getProduct = 15}
--
-- >>> foldMap (replicate 3) [1, 2, 3]
-- [1,1,1,2,2,2,3,3,3]
--
-- When a Monoid's @('<>')@ is lazy in its second argument, 'foldMap' can
-- return a result even from an unbounded structure. For example, lazy
-- accumulation enables "Data.ByteString.Builder" to efficiently serialise
-- large data structures and produce the output incrementally:
--
-- >>> import qualified Data.ByteString.Lazy as L
-- >>> import qualified Data.ByteString.Builder as B
-- >>> let bld :: Int -> B.Builder; bld i = B.intDec i <> B.word8 0x20
-- >>> let lbs = B.toLazyByteString $ foldMap bld [0..]
-- >>> L.take 64 lbs
-- "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24"
--
foldMap :: Monoid m => (a -> m) -> t a -> m
{-# INLINE foldMap #-}
-- This INLINE allows more list functions to fuse. See #9848.
foldMap f = foldr (mappend . f) mempty
-- | A left-associative variant of 'foldMap' that is strict in the
-- accumulator. Use this method for strict reduction when partial
-- results are merged via @('<>')@.
--
-- ==== __Examples__
--
-- Define a 'Monoid' over finite bit strings under 'xor'. Use it to
-- strictly compute the `xor` of a list of 'Int' values.
--
-- >>> :set -XGeneralizedNewtypeDeriving
-- >>> import Data.Bits (Bits, FiniteBits, xor, zeroBits)
-- >>> import Data.Foldable (foldMap')
-- >>> import Numeric (showHex)
-- >>>
-- >>> newtype X a = X a deriving (Eq, Bounded, Enum, Bits, FiniteBits)
-- >>> instance Bits a => Semigroup (X a) where X a <> X b = X (a `xor` b)
-- >>> instance Bits a => Monoid (X a) where mempty = X zeroBits
-- >>>
-- >>> let bits :: [Int]; bits = [0xcafe, 0xfeed, 0xdeaf, 0xbeef, 0x5411]
-- >>> (\ (X a) -> showString "0x" . showHex a $ "") $ foldMap' X bits
-- "0x42"
--
-- @since 4.13.0.0
foldMap' :: Monoid m => (a -> m) -> t a -> m
foldMap' f = foldl' (\ acc a -> acc <> f a) mempty
-- | Right-associative fold of a structure, lazy in the accumulator.
--
-- In the case of lists, 'foldr', when applied to a binary operator, a
-- starting value (typically the right-identity of the operator), and a
-- list, reduces the list using the binary operator, from right to left:
--
-- > foldr f z [x1, x2, ..., xn] == x1 `f` (x2 `f` ... (xn `f` z)...)
--
-- Note that since the head of the resulting expression is produced by an
-- application of the operator to the first element of the list, given an
-- operator lazy in its right argument, 'foldr' can produce a terminating
-- expression from an unbounded list.
--
-- For a general 'Foldable' structure this should be semantically identical
-- to,
--
-- @foldr f z = 'List.foldr' f z . 'toList'@
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> foldr (||) False [False, True, False]
-- True
--
-- >>> foldr (||) False []
-- False
--
-- >>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
-- "foodcba"
--
-- ===== Infinite structures
--
-- ⚠️ Applying 'foldr' to infinite structures usually doesn't terminate.
--
-- It may still terminate under one of the following conditions:
--
-- * the folding function is short-circuiting
-- * the folding function is lazy on its second argument
--
-- ====== Short-circuiting
--
-- @('||')@ short-circuits on 'True' values, so the following terminates
-- because there is a 'True' value finitely far from the left side:
--
-- >>> foldr (||) False (True : repeat False)
-- True
--
-- But the following doesn't terminate:
--
-- >>> foldr (||) False (repeat False ++ [True])
-- * Hangs forever *
--
-- ====== Laziness in the second argument
--
-- Applying 'foldr' to infinite structures terminates when the operator is
-- lazy in its second argument (the initial accumulator is never used in
-- this case, and so could be left 'undefined', but @[]@ is more clear):
--
-- >>> take 5 $ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
-- [1,4,7,10,13]
foldr :: (a -> b -> b) -> b -> t a -> b
foldr f z t = appEndo (foldMap (Endo #. f) t) z
-- | Right-associative fold of a structure, strict in the accumulator.
-- This is rarely what you want.
--
-- @since 4.6.0.0
foldr' :: (a -> b -> b) -> b -> t a -> b
foldr' f z0 xs = foldl f' id xs z0
where f' k x z = k $! f x z
-- | Left-associative fold of a structure, lazy in the accumulator. This
-- is rarely what you want, but can work well for structures with efficient
-- right-to-left sequencing and an operator that is lazy in its left
-- argument.
--
-- In the case of lists, 'foldl', when applied to a binary operator, a
-- starting value (typically the left-identity of the operator), and a
-- list, reduces the list using the binary operator, from left to right:
--
-- > foldl f z [x1, x2, ..., xn] == (...((z `f` x1) `f` x2) `f`...) `f` xn
--
-- Note that to produce the outermost application of the operator the
-- entire input list must be traversed. Like all left-associative folds,
-- 'foldl' will diverge if given an infinite list.
--
-- If you want an efficient strict left-fold, you probably want to use
-- 'foldl'' instead of 'foldl'. The reason for this is that the latter
-- does not force the /inner/ results (e.g. @z \`f\` x1@ in the above
-- example) before applying them to the operator (e.g. to @(\`f\` x2)@).
-- This results in a thunk chain \(\mathcal{O}(n)\) elements long, which
-- then must be evaluated from the outside-in.
--
-- For a general 'Foldable' structure this should be semantically identical
-- to:
--
-- @foldl f z = 'List.foldl' f z . 'toList'@
--
-- ==== __Examples__
--
-- The first example is a strict fold, which in practice is best performed
-- with 'foldl''.
--
-- >>> foldl (+) 42 [1,2,3,4]
-- 52
--
-- Though the result below is lazy, the input is reversed before prepending
-- it to the initial accumulator, so corecursion begins only after traversing
-- the entire input string.
--
-- >>> foldl (\acc c -> c : acc) "abcd" "efgh"
-- "hgfeabcd"
--
-- A left fold of a structure that is infinite on the right cannot
-- terminate, even when for any finite input the fold just returns the
-- initial accumulator:
--
-- >>> foldl (\a _ -> a) 0 $ repeat 1
-- * Hangs forever *
--
foldl :: (b -> a -> b) -> b -> t a -> b
foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
-- There's no point mucking around with coercions here,
-- because flip forces us to build a new function anyway.
-- | Left-associative fold of a structure but with strict application of
-- the operator.
--
-- This ensures that each step of the fold is forced to Weak Head Normal
-- Form before being applied, avoiding the collection of thunks that would
-- otherwise occur. This is often what you want to strictly reduce a
-- finite structure to a single strict result (e.g. 'sum').
--
-- For a general 'Foldable' structure this should be semantically identical
-- to,
--
-- @foldl' f z = 'List.foldl'' f z . 'toList'@
--
-- @since 4.6.0.0
foldl' :: (b -> a -> b) -> b -> t a -> b
foldl' f z0 xs = foldr f' id xs z0
where f' x k z = k $! f z x
-- | A variant of 'foldr' that has no base case,
-- and thus may only be applied to non-empty structures.
--
-- This function is non-total and will raise a runtime exception if the
-- structure happens to be empty.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> foldr1 (+) [1..4]
-- 10
--
-- >>> foldr1 (+) []
-- Exception: Prelude.foldr1: empty list
--
-- >>> foldr1 (+) Nothing
-- *** Exception: foldr1: empty structure
--
-- >>> foldr1 (-) [1..4]
-- -2
--
-- >>> foldr1 (&&) [True, False, True, True]
-- False
--
-- >>> foldr1 (||) [False, False, True, True]
-- True
--
-- >>> foldr1 (+) [1..]
-- * Hangs forever *
foldr1 :: (a -> a -> a) -> t a -> a
foldr1 f xs = fromMaybe (errorWithoutStackTrace "foldr1: empty structure")
(foldr mf Nothing xs)
where
mf x m = Just (case m of
Nothing -> x
Just y -> f x y)
-- | A variant of 'foldl' that has no base case,
-- and thus may only be applied to non-empty structures.
--
-- This function is non-total and will raise a runtime exception if the
-- structure happens to be empty.
--
-- @'foldl1' f = 'List.foldl1' f . 'toList'@
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> foldl1 (+) [1..4]
-- 10
--
-- >>> foldl1 (+) []
-- *** Exception: Prelude.foldl1: empty list
--
-- >>> foldl1 (+) Nothing
-- *** Exception: foldl1: empty structure
--
-- >>> foldl1 (-) [1..4]
-- -8
--
-- >>> foldl1 (&&) [True, False, True, True]
-- False
--
-- >>> foldl1 (||) [False, False, True, True]
-- True
--
-- >>> foldl1 (+) [1..]
-- * Hangs forever *
foldl1 :: (a -> a -> a) -> t a -> a
foldl1 f xs = fromMaybe (errorWithoutStackTrace "foldl1: empty structure")
(foldl mf Nothing xs)
where
mf m y = Just (case m of
Nothing -> y
Just x -> f x y)
-- | List of elements of a structure, from left to right. If the entire
-- list is intended to be reduced via a fold, just fold the structure
-- directly bypassing the list.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> toList Nothing
-- []
--
-- >>> toList (Just 42)
-- [42]
--
-- >>> toList (Left "foo")
-- []
--
-- >>> toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8)))
-- [5,17,12,8]
--
-- For lists, 'toList' is the identity:
--
-- >>> toList [1, 2, 3]
-- [1,2,3]
--
-- @since 4.8.0.0
toList :: t a -> [a]
{-# INLINE toList #-}
toList t = build (\ c n -> foldr c n t)
-- | Test whether the structure is empty. The default implementation is
-- Left-associative and lazy in both the initial element and the
-- accumulator. Thus optimised for structures where the first element can
-- be accessed in constant time. Structures where this is not the case
-- should have a non-default implementation.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> null []
-- True
--
-- >>> null [1]
-- False
--
-- 'null' is expected to terminate even for infinite structures.
-- The default implementation terminates provided the structure
-- is bounded on the left (there is a left-most element).
--
-- >>> null [1..]
-- False
--
-- @since 4.8.0.0
null :: t a -> Bool
null = foldr (\_ _ -> False) True
-- | Returns the size/length of a finite structure as an 'Int'. The
-- default implementation just counts elements starting with the left-most.
-- Instances for structures that can compute the element count faster
-- than via element-by-element counting, should provide a specialised
-- implementation.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> length []
-- 0
--
-- >>> length ['a', 'b', 'c']
-- 3
-- >>> length [1..]
-- * Hangs forever *
--
-- @since 4.8.0.0
length :: t a -> Int
length = foldl' (\c _ -> c+1) 0
-- | Does the element occur in the structure?
--
-- Note: 'elem' is often used in infix form.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> 3 `elem` []
-- False
--
-- >>> 3 `elem` [1,2]
-- False
--
-- >>> 3 `elem` [1,2,3,4,5]
-- True
--
-- For infinite structures, the default implementation of 'elem'
-- terminates if the sought-after value exists at a finite distance
-- from the left side of the structure:
--
-- >>> 3 `elem` [1..]
-- True
--
-- >>> 3 `elem` ([4..] ++ [3])
-- * Hangs forever *
--
-- @since 4.8.0.0
elem :: Eq a => a -> t a -> Bool
elem = any . (==)
-- | The largest element of a non-empty structure.
--
-- This function is non-total and will raise a runtime exception if the
-- structure happens to be empty. A structure that supports random access
-- and maintains its elements in order should provide a specialised
-- implementation to return the maximum in faster than linear time.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> maximum [1..10]
-- 10
--
-- >>> maximum []
-- *** Exception: Prelude.maximum: empty list
--
-- >>> maximum Nothing
-- *** Exception: maximum: empty structure
--
-- @since 4.8.0.0
maximum :: forall a . Ord a => t a -> a
maximum = fromMaybe (errorWithoutStackTrace "maximum: empty structure") .
getMax . foldMap' (Max #. (Just :: a -> Maybe a))
{-# INLINEABLE maximum #-}
-- | The least element of a non-empty structure.
--
-- This function is non-total and will raise a runtime exception if the
-- structure happens to be empty. A structure that supports random access
-- and maintains its elements in order should provide a specialised
-- implementation to return the minimum in faster than linear time.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> minimum [1..10]
-- 1
--
-- >>> minimum []
-- *** Exception: Prelude.minimum: empty list
--
-- >>> minimum Nothing
-- *** Exception: minimum: empty structure
--
-- @since 4.8.0.0
minimum :: forall a . Ord a => t a -> a
minimum = fromMaybe (errorWithoutStackTrace "minimum: empty structure") .
getMin . foldMap' (Min #. (Just :: a -> Maybe a))
{-# INLINEABLE minimum #-}
-- | The 'sum' function computes the sum of the numbers of a structure.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> sum []
-- 0
--
-- >>> sum [42]
-- 42
--
-- >>> sum [1..10]
-- 55
--
-- >>> sum [4.1, 2.0, 1.7]
-- 7.8
--
-- >>> sum [1..]
-- * Hangs forever *
--
-- @since 4.8.0.0
sum :: Num a => t a -> a
sum = getSum #. foldMap' Sum
{-# INLINEABLE sum #-}
-- | The 'product' function computes the product of the numbers of a
-- structure.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> product []
-- 1
--
-- >>> product [42]
-- 42
--
-- >>> product [1..10]
-- 3628800
--
-- >>> product [4.1, 2.0, 1.7]
-- 13.939999999999998
--
-- >>> product [1..]
-- * Hangs forever *
--
-- @since 4.8.0.0
product :: Num a => t a -> a
product = getProduct #. foldMap' Product
{-# INLINEABLE product #-}
-- instances for Prelude types
-- | @since 2.01
instance Foldable Maybe where
foldMap = maybe mempty
foldr _ z Nothing = z
foldr f z (Just x) = f x z
foldl _ z Nothing = z
foldl f z (Just x) = f z x
-- | @since 2.01
instance Foldable [] where
elem = List.elem
foldl = List.foldl
foldl' = List.foldl'
foldl1 = List.foldl1
foldr = List.foldr
foldr1 = List.foldr1
length = List.length
maximum = List.maximum
minimum = List.minimum
null = List.null
product = List.product
sum = List.sum
toList = id
-- | @since 4.9.0.0
instance Foldable NonEmpty where
foldr f z ~(a :| as) = f a (List.foldr f z as)
foldl f z (a :| as) = List.foldl f (f z a) as
foldl1 f (a :| as) = List.foldl f a as
-- GHC isn't clever enough to transform the default definition
-- into anything like this, so we'd end up shuffling a bunch of
-- Maybes around.
foldr1 f (p :| ps) = foldr go id ps p
where
go x r prev = f prev (r x)
-- We used to say
--
-- length (_ :| as) = 1 + length as
--
-- but the default definition is better, counting from 1.
--
-- The default definition also works great for null and foldl'.
-- As usual for cons lists, foldr' is basically hopeless.
foldMap f ~(a :| as) = f a `mappend` foldMap f as
fold ~(m :| ms) = m `mappend` fold ms
toList ~(a :| as) = a : as
-- | @since 4.7.0.0
instance Foldable (Either a) where
foldMap _ (Left _) = mempty
foldMap f (Right y) = f y
foldr _ z (Left _) = z
foldr f z (Right y) = f y z
length (Left _) = 0
length (Right _) = 1
null = isLeft
-- | @since 4.15
deriving instance Foldable Solo
-- | @since 4.7.0.0
instance Foldable ((,) a) where
foldMap f (_, y) = f y
foldr f z (_, y) = f y z
length _ = 1
null _ = False
-- | @since 4.8.0.0
instance Foldable (Array i) where
foldr = foldrElems
foldl = foldlElems
foldl' = foldlElems'
foldr' = foldrElems'
foldl1 = foldl1Elems
foldr1 = foldr1Elems
toList = elems
length = numElements
null a = numElements a == 0
-- | @since 4.7.0.0
instance Foldable Proxy where
foldMap _ _ = mempty
{-# INLINE foldMap #-}
fold _ = mempty
{-# INLINE fold #-}
foldr _ z _ = z
{-# INLINE foldr #-}
foldl _ z _ = z
{-# INLINE foldl #-}
foldl1 _ _ = errorWithoutStackTrace "foldl1: Proxy"
foldr1 _ _ = errorWithoutStackTrace "foldr1: Proxy"
length _ = 0
null _ = True
elem _ _ = False
sum _ = 0
product _ = 1
-- | @since 4.8.0.0
instance Foldable Dual where
foldMap = coerce
elem = (. getDual) #. (==)
foldl = coerce
foldl' = coerce
foldl1 _ = getDual
foldr f z (Dual x) = f x z
foldr' = foldr
foldr1 _ = getDual
length _ = 1
maximum = getDual
minimum = getDual
null _ = False
product = getDual
sum = getDual
toList (Dual x) = [x]
-- | @since 4.8.0.0
instance Foldable Sum where
foldMap = coerce
elem = (. getSum) #. (==)
foldl = coerce
foldl' = coerce
foldl1 _ = getSum
foldr f z (Sum x) = f x z
foldr' = foldr
foldr1 _ = getSum
length _ = 1
maximum = getSum
minimum = getSum
null _ = False
product = getSum
sum = getSum
toList (Sum x) = [x]
-- | @since 4.8.0.0
instance Foldable Product where
foldMap = coerce
elem = (. getProduct) #. (==)
foldl = coerce
foldl' = coerce
foldl1 _ = getProduct
foldr f z (Product x) = f x z
foldr' = foldr
foldr1 _ = getProduct
length _ = 1
maximum = getProduct
minimum = getProduct
null _ = False
product = getProduct
sum = getProduct
toList (Product x) = [x]
-- | @since 4.8.0.0
instance Foldable First where
foldMap f = foldMap f . getFirst
-- | @since 4.8.0.0
instance Foldable Last where
foldMap f = foldMap f . getLast
-- | @since 4.12.0.0
instance (Foldable f) => Foldable (Alt f) where
foldMap f = foldMap f . getAlt
-- | @since 4.12.0.0
instance (Foldable f) => Foldable (Ap f) where
foldMap f = foldMap f . getAp
-- Instances for GHC.Generics
-- | @since 4.9.0.0
instance Foldable U1 where
foldMap _ _ = mempty
{-# INLINE foldMap #-}
fold _ = mempty
{-# INLINE fold #-}
foldr _ z _ = z
{-# INLINE foldr #-}
foldl _ z _ = z
{-# INLINE foldl #-}
foldl1 _ _ = errorWithoutStackTrace "foldl1: U1"
foldr1 _ _ = errorWithoutStackTrace "foldr1: U1"
length _ = 0
null _ = True
elem _ _ = False
sum _ = 0
product _ = 1
-- | @since 4.9.0.0
deriving instance Foldable V1
-- | @since 4.9.0.0
deriving instance Foldable Par1
-- | @since 4.9.0.0
deriving instance Foldable f => Foldable (Rec1 f)
-- | @since 4.9.0.0
deriving instance Foldable (K1 i c)
-- | @since 4.9.0.0
deriving instance Foldable f => Foldable (M1 i c f)
-- | @since 4.9.0.0
deriving instance (Foldable f, Foldable g) => Foldable (f :+: g)
-- | @since 4.9.0.0
deriving instance (Foldable f, Foldable g) => Foldable (f :*: g)
-- | @since 4.9.0.0
deriving instance (Foldable f, Foldable g) => Foldable (f :.: g)
-- | @since 4.9.0.0
deriving instance Foldable UAddr
-- | @since 4.9.0.0
deriving instance Foldable UChar
-- | @since 4.9.0.0
deriving instance Foldable UDouble
-- | @since 4.9.0.0
deriving instance Foldable UFloat
-- | @since 4.9.0.0
deriving instance Foldable UInt
-- | @since 4.9.0.0
deriving instance Foldable UWord
-- Instances for Data.Ord
-- | @since 4.12.0.0
deriving instance Foldable Down
-- | Monadic fold over the elements of a structure. This type of fold is
-- left-associative in the monadic effects, and right-associative in the output
-- value.
--
-- Given a structure @t@ with elements @(a, b, c, ..., x, y)@, the result of
-- a fold with an operator function @f@ is equivalent to:
--
-- > foldrM f z t = do { yy <- f y z; xx <- f x yy; ... ; bb <- f b cc; f a bb }
--
-- If in a 'MonadPlus' the bind short-circuits, the evaluated effects will be
-- from a tail of the sequence. If you want to evaluate the monadic effects in
-- left-to-right order, or perhaps be able to short-circuit after an initial
-- sequence of elements, you'll need to use `foldlM` instead.
--
-- If the monadic effects don't short-circuit, the outer-most application of
-- @f@ is to left-most element @a@, so that, ignoring effects, the result looks
-- like a right fold:
--
-- > a `f` (b `f` (c `f` (... (x `f` (y `f` z))))).
--
-- and yet, left-associative monadic binds, rather than right-associative
-- applications of @f@, sequence the computation.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> let f i acc = do { print i ; return $ i : acc }
-- >>> foldrM f [] [0..3]
-- 3
-- 2
-- 1
-- 0
-- [0,1,2,3]
--
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
foldrM f z0 xs = foldl c return xs z0
-- See Note [List fusion and continuations in 'c']
where c k x z = f x z >>= k
{-# INLINE c #-}
-- | Monadic fold over the elements of a structure. This type of fold is
-- right-associative in the monadic effects, and left-associative in the output
-- value.
--
-- Given a structure @t@ with elements @(a, b, ..., w, x, y)@, the result of
-- a fold with an operator function @f@ is equivalent to:
--
-- > foldlM f z t = do { aa <- f z a; bb <- f aa b; ... ; xx <- f ww x; f xx y }
--
-- If in a 'MonadPlus' the bind short-circuits, the evaluated effects will be
-- from an initial portion of the sequence. If you want to evaluate the
-- monadic effects in right-to-left order, or perhaps be able to short-circuit
-- after processing a tail of the sequence of elements, you'll need to use
-- `foldrM` instead.
--
-- If the monadic effects don't short-circuit, the outer-most application of
-- @f@ is to the right-most element @y@, so that, ignoring effects, the result
-- looks like a left fold:
--
-- > ((((z `f` a) `f` b) ... `f` w) `f` x) `f` y
--
-- and yet, right-associative monadic binds, rather than left-associative
-- applications of @f@, sequence the computation.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> let f a e = do { print e ; return $ e : a }
-- >>> foldlM f [] [0..3]
-- 0
-- 1
-- 2
-- 3
-- [3,2,1,0]
--
foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
foldlM f z0 xs = foldr c return xs z0
-- See Note [List fusion and continuations in 'c']
where c x k z = f z x >>= k
{-# INLINE c #-}
-- | Map each element of a structure to an 'Applicative' action, evaluate these
-- actions from left to right, and ignore the results. For a version that
-- doesn't ignore the results see 'Data.Traversable.traverse'.
--
-- 'traverse_' is just like 'mapM_', but generalised to 'Applicative' actions.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> traverse_ print ["Hello", "world", "!"]
-- "Hello"
-- "world"
-- "!"
traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
traverse_ f = foldr c (pure ())
-- See Note [List fusion and continuations in 'c']
where c x k = f x *> k
{-# INLINE c #-}
-- | 'for_' is 'traverse_' with its arguments flipped. For a version
-- that doesn't ignore the results see 'Data.Traversable.for'. This
-- is 'forM_' generalised to 'Applicative' actions.
--
-- 'for_' is just like 'forM_', but generalised to 'Applicative' actions.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> for_ [1..4] print
-- 1
-- 2
-- 3
-- 4
for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
{-# INLINE for_ #-}
for_ = flip traverse_
-- | Map each element of a structure to a monadic action, evaluate
-- these actions from left to right, and ignore the results. For a
-- version that doesn't ignore the results see
-- 'Data.Traversable.mapM'.
--
-- 'mapM_' is just like 'traverse_', but specialised to monadic actions.
--
mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
mapM_ f = foldr c (return ())
-- See Note [List fusion and continuations in 'c']
where c x k = f x >> k
{-# INLINE c #-}
-- | 'forM_' is 'mapM_' with its arguments flipped. For a version that
-- doesn't ignore the results see 'Data.Traversable.forM'.
--
-- 'forM_' is just like 'for_', but specialised to monadic actions.
--
forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
{-# INLINE forM_ #-}
forM_ = flip mapM_
-- | Evaluate each action in the structure from left to right, and
-- ignore the results. For a version that doesn't ignore the results
-- see 'Data.Traversable.sequenceA'.
--
-- 'sequenceA_' is just like 'sequence_', but generalised to 'Applicative'
-- actions.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> sequenceA_ [print "Hello", print "world", print "!"]
-- "Hello"
-- "world"
-- "!"
sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f ()
sequenceA_ = foldr c (pure ())
-- See Note [List fusion and continuations in 'c']
where c m k = m *> k
{-# INLINE c #-}
-- | Evaluate each monadic action in the structure from left to right,
-- and ignore the results. For a version that doesn't ignore the
-- results see 'Data.Traversable.sequence'.
--
-- 'sequence_' is just like 'sequenceA_', but specialised to monadic
-- actions.
--
sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()
sequence_ = foldr c (return ())
-- See Note [List fusion and continuations in 'c']
where c m k = m >> k
{-# INLINE c #-}
-- | The sum of a collection of actions, generalizing 'concat'.
--
-- 'asum' is just like 'msum', but generalised to 'Alternative'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> asum [Just "Hello", Nothing, Just "World"]
-- Just "Hello"
asum :: (Foldable t, Alternative f) => t (f a) -> f a
{-# INLINE asum #-}
asum = foldr (<|>) empty
-- | The sum of a collection of actions, generalizing 'concat'.
--
-- 'msum' is just like 'asum', but specialised to 'MonadPlus'.
--
msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
{-# INLINE msum #-}
msum = asum
-- | The concatenation of all the elements of a container of lists.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> concat (Just [1, 2, 3])
-- [1,2,3]
--
-- >>> concat (Left 42)
-- []
--
-- >>> concat [[1, 2, 3], [4, 5], [6], []]
-- [1,2,3,4,5,6]
--
concat :: Foldable t => t [a] -> [a]
concat xs = build (\c n -> foldr (\x y -> foldr c y x) n xs)
{-# INLINE concat #-}
-- | Map a function over all the elements of a container and concatenate
-- the resulting lists.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> concatMap (take 3) [[1..], [10..], [100..], [1000..]]
-- [1,2,3,10,11,12,100,101,102,1000,1001,1002]
--
-- >>> concatMap (take 3) (Just [1..])
-- [1,2,3]
concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
concatMap f xs = build (\c n -> foldr (\x b -> foldr c b (f x)) n xs)
{-# INLINE concatMap #-}
-- These use foldr rather than foldMap to avoid repeated concatenation.
-- | 'and' returns the conjunction of a container of Bools. For the
-- result to be 'True', the container must be finite; 'False', however,
-- results from a 'False' value finitely far from the left end.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> and []
-- True
--
-- >>> and [True]
-- True
--
-- >>> and [False]
-- False
--
-- >>> and [True, True, False]
-- False
--
-- >>> and (False : repeat True) -- Infinite list [False,True,True,True,...
-- False
--
-- >>> and (repeat True)
-- * Hangs forever *
and :: Foldable t => t Bool -> Bool
and = getAll #. foldMap All
-- | 'or' returns the disjunction of a container of Bools. For the
-- result to be 'False', the container must be finite; 'True', however,
-- results from a 'True' value finitely far from the left end.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> or []
-- False
--
-- >>> or [True]
-- True
--
-- >>> or [False]
-- False
--
-- >>> or [True, True, False]
-- True
--
-- >>> or (True : repeat False) -- Infinite list [True,False,False,False,...
-- True
--
-- >>> or (repeat False)
-- * Hangs forever *
or :: Foldable t => t Bool -> Bool
or = getAny #. foldMap Any
-- | Determines whether any element of the structure satisfies the predicate.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> any (> 3) []
-- False
--
-- >>> any (> 3) [1,2]
-- False
--
-- >>> any (> 3) [1,2,3,4,5]
-- True
--
-- >>> any (> 3) [1..]
-- True
--
-- >>> any (> 3) [0, -1..]
-- * Hangs forever *
any :: Foldable t => (a -> Bool) -> t a -> Bool
any p = getAny #. foldMap (Any #. p)
-- | Determines whether all elements of the structure satisfy the predicate.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> all (> 3) []
-- True
--
-- >>> all (> 3) [1,2]
-- False
--
-- >>> all (> 3) [1,2,3,4,5]
-- False
--
-- >>> all (> 3) [1..]
-- False
--
-- >>> all (> 3) [4..]
-- * Hangs forever *
all :: Foldable t => (a -> Bool) -> t a -> Bool
all p = getAll #. foldMap (All #. p)
-- | The largest element of a non-empty structure with respect to the
-- given comparison function.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
-- "Longest"
-- See Note [maximumBy/minimumBy space usage]
maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
maximumBy cmp = fromMaybe (errorWithoutStackTrace "maximumBy: empty structure")
. foldl' max' Nothing
where
max' mx y = Just $! case mx of
Nothing -> y
Just x -> case cmp x y of
GT -> x
_ -> y
{-# INLINEABLE maximumBy #-}
-- | The least element of a non-empty structure with respect to the
-- given comparison function.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
-- "!"
-- See Note [maximumBy/minimumBy space usage]
minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
minimumBy cmp = fromMaybe (errorWithoutStackTrace "minimumBy: empty structure")
. foldl' min' Nothing
where
min' mx y = Just $! case mx of
Nothing -> y
Just x -> case cmp x y of
GT -> y
_ -> x
{-# INLINEABLE minimumBy #-}
-- | 'notElem' is the negation of 'elem'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> 3 `notElem` []
-- True
--
-- >>> 3 `notElem` [1,2]
-- True
--
-- >>> 3 `notElem` [1,2,3,4,5]
-- False
--
-- For infinite structures, 'notElem' terminates if the value exists at a
-- finite distance from the left side of the structure:
--
-- >>> 3 `notElem` [1..]
-- False
--
-- >>> 3 `notElem` ([4..] ++ [3])
-- * Hangs forever *
notElem :: (Foldable t, Eq a) => a -> t a -> Bool
notElem x = not . elem x
-- | The 'find' function takes a predicate and a structure and returns
-- the leftmost element of the structure matching the predicate, or
-- 'Nothing' if there is no such element.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> find (> 42) [0, 5..]
-- Just 45
--
-- >>> find (> 12) [1..7]
-- Nothing
find :: Foldable t => (a -> Bool) -> t a -> Maybe a
find p = getFirst . foldMap (\ x -> First (if p x then Just x else Nothing))
{-
Note [List fusion and continuations in 'c']
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Suppose we define
mapM_ f = foldr ((>>) . f) (return ())
(this is the way it used to be).
Now suppose we want to optimise the call
mapM_ <big> (build g)
where
g c n = ...(c x1 y1)...(c x2 y2)....n...
GHC used to proceed like this:
mapM_ <big> (build g)
= { Definition of mapM_ }
foldr ((>>) . <big>) (return ()) (build g)
= { foldr/build rule }
g ((>>) . <big>) (return ())
= { Inline g }
let c = (>>) . <big>
n = return ()
in ...(c x1 y1)...(c x2 y2)....n...
The trouble is that `c`, being big, will not be inlined. And that can
be absolutely terrible for performance, as we saw in #8763.
It's much better to define
mapM_ f = foldr c (return ())
where
c x k = f x >> k
{-# INLINE c #-}
Now we get
mapM_ <big> (build g)
= { inline mapM_ }
foldr c (return ()) (build g)
where c x k = f x >> k
{-# INLINE c #-}
f = <big>
Notice that `f` does not inline into the RHS of `c`,
because the INLINE pragma stops it; see
Note [Simplifying inside stable unfoldings] in GHC.Core.Opt.Simplify.Utils.
Continuing:
= { foldr/build rule }
g c (return ())
where ...
c x k = f x >> k
{-# INLINE c #-}
f = <big>
= { inline g }
...(c x1 y1)...(c x2 y2)....n...
where c x k = f x >> k
{-# INLINE c #-}
f = <big>
n = return ()
Now, crucially, `c` does inline
= { inline c }
...(f x1 >> y1)...(f x2 >> y2)....n...
where f = <big>
n = return ()
And all is well! The key thing is that the fragment
`(f x1 >> y1)` is inlined into the body of the builder
`g`.
-}
{-
Note [maximumBy/minimumBy space usage]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
When the type signatures of maximumBy and minimumBy were generalized to work
over any Foldable instance (instead of just lists), they were defined using
foldr1. This was problematic for space usage, as the semantics of maximumBy
and minimumBy essentially require that they examine every element of the
data structure. Using foldr1 to examine every element results in space usage
proportional to the size of the data structure. For the common case of lists,
this could be particularly bad (see #10830).
For the common case of lists, switching the implementations of maximumBy and
minimumBy to foldl1 solves the issue, assuming GHC's strictness analysis can then
make these functions only use O(1) stack space. As of base 4.16, we have
switched to employing foldl' over foldl1, not relying on GHC's optimiser. See
https://gitlab.haskell.org/ghc/ghc/-/issues/17867 for more context.
-}
--------------
-- $overview
--
-- #overview#
-- Foldable structures are reduced to a summary value by accumulating
-- contributions to the result one element at a time.
--
-- == Left and right folds
--
-- #leftright#
-- Merging the contribution of the current element with an accumulator value
-- from a partial result is performed by an /operator/ function, either
-- explicitly provided by the caller as in `foldr`, implicit count as in
-- `length`, or partly implicit as in `foldMap` (where each element is mapped
-- into a 'Monoid', and the monoid's `mappend` operator performs the merge).
--
-- A key distinction is between left-associative and right-associative
-- folds:
--
-- * In left-associative folds the accumulator is a partial fold over the
-- elements that __precede__ the current element, and is passed to the
-- operator as its first (left) argument. The outer-most application of the
-- operator merges the contribution of the last element of the structure with
-- the contributions of all its predecessors.
--
-- * In right-associative folds the accumulator is a partial fold over the
-- elements that __follow__ the current element, and is passed to the
-- operator as its second (right) argument. The outer-most application of
-- the operator merges the contribution of the first element of the structure
-- with the contributions of all its successors.
--
-- These two types of folds are typified by the left-associative strict
-- 'foldl'' and the right-associative lazy `foldr`.
--
-- @
-- 'foldl'' :: Foldable t => (b -> a -> b) -> b -> t a -> b
-- `foldr` :: Foldable t => (a -> b -> b) -> b -> t a -> b
-- @
--
-- Example usage:
--
-- >>> foldl' (+) 0 [1..100]
-- 5050
-- >>> foldr (&&) True (repeat False)
-- False
--
-- The first argument of both is an explicit /operator/ that merges the
-- contribution of an element of the structure with a partial fold over,
-- respectively, either the preceding or following elements of the structure.
--
-- The second argument of both is an initial accumulator value @z@ of type
-- @b@. This is the result of the fold when the structure is empty.
-- When the structure is non-empty, this is the accumulator value merged with
-- the first element in left-associative folds, or with the last element in
-- right-associative folds.
--
-- The third and final argument is a @Foldable@ structure containing elements
-- @(a, b, c, …)@.
--
-- * __'foldl''__ takes an operator function of the form:
--
-- @
-- f :: b -- accumulated fold of the initial elements
-- -> a -- current element
-- -> b -- updated fold, inclusive of current element
-- @
--
-- If the structure's last element is @y@, the result of the fold is:
--
-- @
-- g y . … . g c . g b . g a $ z
-- where g element !acc = f acc element
-- @
--
-- Since 'foldl'' is strict in the accumulator, this is always
-- a [strict](#strict) reduction with no opportunity for early return or
-- intermediate results. The structure must be finite, since no result is
-- returned until the last element is processed. The advantage of
-- strictness is space efficiency: the final result can be computed without
-- storing a potentially deep stack of lazy intermediate results.
--
-- * __`foldr`__ takes an operator function of the form:
--
-- @
-- f :: a -- current element
-- -> b -- accumulated fold of the remaining elements
-- -> b -- updated fold, inclusive of current element
-- @
--
-- the result of the fold is:
--
-- @f a . f b . f c . … $ z@
--
-- If each call of @f@ on the current element @e@, (referenced as @(f e)@
-- below) returns a structure in which its second argument is captured in a
-- lazily-evaluated component, then the fold of the remaining elements is
-- available to the caller of `foldr` as a pending computation (thunk) that
-- is computed only when that component is evaluated.
--
-- Alternatively, if any of the @(f e)@ ignore their second argument, the
-- fold stops there, with the remaining elements unused. As a result,
-- `foldr` is well suited to define both [corecursive](#corec)
-- and [short-circuit](#short) reductions.
--
-- When the operator is always strict in the second argument, 'foldl'' is
-- generally a better choice than `foldr`. When `foldr` is called with a
-- strict operator, evaluation cannot begin until the last element is
-- reached, by which point a deep stack of pending function applications
-- may have been built up in memory.
--
-- $chirality
--
-- #chirality#
-- Foldable structures are generally expected to be efficiently iterable from
-- left to right. Right-to-left iteration may be substantially more costly, or
-- even impossible (as with, for example, infinite lists). The text in the
-- sections that follow that suggests performance differences between
-- left-associative and right-associative folds assumes /left-handed/
-- structures in which left-to-right iteration is cheaper than right-to-left
-- iteration.
--
-- In finite structures for which right-to-left sequencing no less efficient
-- than left-to-right sequencing, there is no inherent performance distinction
-- between left-associative and right-associative folds. If the structure's
-- @Foldable@ instance takes advantage of this symmetry to also make strict
-- right folds space-efficient and lazy left folds corecursive, one need only
-- take care to choose either a strict or lazy method for the task at hand.
--
-- Foldable instances for symmetric structures should strive to provide equally
-- performant left-associative and right-associative interfaces. The main
-- limitations are:
--
-- * The lazy 'fold', 'foldMap' and 'toList' methods have no right-associative
-- counterparts.
-- * The strict 'foldMap'' method has no left-associative counterpart.
--
-- Thus, for some foldable structures 'foldr'' is just as efficient as 'foldl''
-- for strict reduction, and 'foldl' may be just as appropriate for corecursive
-- folds as 'foldr'.
--
-- Finally, in some less common structures (e.g. /snoc/ lists) right to left
-- iterations are cheaper than left to right. Such structures are poor
-- candidates for a @Foldable@ instance, and are perhaps best handled via their
-- type-specific interfaces. If nevertheless a @Foldable@ instance is
-- provided, the material in the sections that follow applies to these also, by
-- replacing each method with one with the opposite associativity (when
-- available) and switching the order of arguments in the /operator/ function.
--
-- You may need to pay careful attention to strictness of the fold's /operator/
-- when its strictness is different between its first and second argument.
-- For example, while @('+')@ is expected to be commutative and strict in both
-- arguments, the list concatenation operator @('++')@ is not commutative and
-- is only strict in the initial constructor of its first argument. The fold:
--
-- > myconcat xs = foldr (\a b -> a ++ b) [] xs
--
-- is subtantially cheaper (linear in the length of the consumed portion of the
-- final list, thus e.g. constant time/space for just the first element) than:
--
-- > revconcat xs = foldr (\a b -> b ++ a) [] xs
--
-- In which the total cost scales up with both the number of lists combined and
-- the number of elements ultimately consumed. A more efficient way to combine
-- lists in reverse order, is to use:
--
-- > revconcat = foldr (++) [] . reverse
--------------
-- $reduction
--
-- As observed in the [above description](#leftright) of left and right folds,
-- there are three general ways in which a structure can be reduced to a
-- summary value:
--
-- * __Recursive__ reduction, which is strict in all the elements of the
-- structure. This produces a single final result only after processing the
-- entire input structure, and so the input must be finite.
--
-- * __Corecursion__, which yields intermediate results as it encounters
-- additional input elements. Lazy processing of the remaining elements
-- makes the intermediate results available even before the rest of the
-- input is processed. The input may be unbounded, and the caller can
-- stop processing intermediate results early.
--
-- * __Short-circuit__ reduction, which examines some initial sequence of the
-- input elements, but stops once a termination condition is met, returning a
-- final result based only on the elements considered up to that point. The
-- remaining elements are not considered. The input should generally be
-- finite, because the termination condition might otherwise never be met.
--
-- Whether a fold is recursive, corecursive or short-circuiting can depend on
-- both the method chosen to perform the fold and on the operator passed to
-- that method (which may be implicit, as with the `mappend` method of a monoid
-- instance).
--
-- There are also hybrid cases, where the method and/or operator are not well
-- suited to the task at hand, resulting in a fold that fails to yield
-- incremental results until the entire input is processed, or fails to
-- strictly evaluate results as it goes, deferring all the work to the
-- evaluation of a large final thunk. Such cases should be avoided, either by
-- selecting a more appropriate @Foldable@ method, or by tailoring the operator
-- to the chosen method.
--
-- The distinction between these types of folds is critical, both in deciding
-- which @Foldable@ method to use to perform the reduction efficiently, and in
-- writing @Foldable@ instances for new structures. Below is a more detailed
-- overview of each type.
--------------
-- $strict
-- #strict#
--
-- Common examples of strict recursive reduction are the various /aggregate/
-- functions, like 'sum', 'product', 'length', as well as more complex
-- summaries such as frequency counts. These functions return only a single
-- value after processing the entire input structure. In such cases, lazy
-- processing of the tail of the input structure is generally not only
-- unnecessary, but also inefficient. Thus, these and similar folds should be
-- implemented in terms of strict left-associative @Foldable@ methods (typically
-- 'foldl'') to perform an efficient reduction in constant space.
--
-- Conversely, an implementation of @Foldable@ for a new structure should
-- ensure that 'foldl'' actually performs a strict left-associative reduction.
--
-- The 'foldMap'' method is a special case of 'foldl'', in which the initial
-- accumulator is `mempty` and the operator is @mappend . f@, where @f@ maps
-- each input element into the 'Monoid' in question. Therefore, 'foldMap'' is
-- an appropriate choice under essentially the same conditions as 'foldl'', and
-- its implementation for a given @Foldable@ structure should also be a strict
-- left-associative reduction.
--
-- While the examples below are not necessarily the most optimal definitions of
-- the intended functions, they are all cases in which 'foldMap'' is far more
-- appropriate (as well as more efficient) than the lazy `foldMap`.
--
-- > length = getSum . foldMap' (const (Sum 1))
-- > sum = getSum . foldMap' Sum
-- > product = getProduct . foldMap' Product
--
-- [ The actual default definitions employ coercions to optimise out
-- 'getSum' and 'getProduct'. ]
--------------
-- $strictlist
--
-- The full list of strict recursive functions in this module is:
--
-- * Provided the operator is strict in its left argument:
--
-- @'foldl'' :: Foldable t => (b -> a -> b) -> b -> t a -> b@
--
-- * Provided `mappend` is strict in its left argument:
--
-- @'foldMap'' :: (Foldable t, Monoid m) => (a -> m) -> t a -> m@
--
-- * Provided the instance is correctly defined:
--
-- @
-- `length` :: Foldable t => t a -> Int
-- `sum` :: (Foldable t, Num a) => t a -> a
-- `product` :: (Foldable t, Num a) => t a -> a
-- `maximum` :: (Foldable t, Ord a) => t a -> a
-- `minimum` :: (Foldable t, Ord a) => t a -> a
-- `maximumBy` :: Foldable t => (a -> a -> Ordering) -> t a -> a
-- `minimumBy` :: Foldable t => (a -> a -> Ordering) -> t a -> a
-- @
--------------
-- $lazy
--
-- #corec#
-- Common examples of lazy corecursive reduction are functions that map and
-- flatten a structure to a lazy stream of result values, i.e. an iterator
-- over the transformed input elements. In such cases, it is important to
-- choose a @Foldable@ method that is lazy in the tail of the structure, such
-- as `foldr` (or `foldMap`, if the result @Monoid@ has a lazy `mappend` as
-- with e.g. ByteString Builders).
--
-- Conversely, an implementation of `foldr` for a structure that can
-- accommodate a large (and possibly unbounded) number of elements is expected
-- to be lazy in the tail of the input, allowing operators that are lazy in the
-- accumulator to yield intermediate results incrementally. Such folds are
-- right-associative, with the tail of the stream returned as a lazily
-- evaluated component of the result (an element of a tuple or some other
-- non-strict constructor, e.g. the @(:)@ constructor for lists).
--
-- The @toList@ function below lazily transforms a @Foldable@ structure to a
-- List. Note that this transformation may be lossy, e.g. for a keyed
-- container (@Map@, @HashMap@, …) the output stream holds only the
-- values, not the keys. Lossless transformations to\/from lists of @(key,
-- value)@ pairs are typically available in the modules for the specific
-- container types.
--
-- > toList = foldr (:) []
--
-- A more complex example is concatenation of a list of lists expressed as a
-- nested right fold (bypassing @('++')@). We can check that the definition is
-- indeed lazy by folding an infinite list of lists, and taking an initial
-- segment.
--
-- >>> myconcat = foldr (\x z -> foldr (:) z x) []
-- >>> take 15 $ myconcat $ map (\i -> [0..i]) [0..]
-- [0,0,1,0,1,2,0,1,2,3,0,1,2,3,4]
--
-- Of course in this case another way to achieve the same result is via a
-- list comprehension:
--
-- > myconcat xss = [x | xs <- xss, x <- xs]
--------------
-- $lazylist
--
-- The full list of lazy corecursive functions in this module is:
--
-- * Provided the reduction function is lazy in its second argument,
-- (otherwise best to use a strict recursive reduction):
--
-- @
-- `foldr` :: Foldable t => (a -> b -> b) -> b -> t a -> b
-- `foldr1` :: Foldable t => (a -> a -> a) -> t a -> a
-- @
--
-- * Provided the 'Monoid' `mappend` is lazy in its second argument
-- (otherwise best to use a strict recursive reduction):
--
-- @
-- `fold` :: Foldable t => Monoid m => t m -> m
-- `foldMap` :: Foldable t => Monoid m => (a -> m) -> t a -> m
-- @
--
-- * Provided the instance is correctly defined:
--
-- @
-- `toList` :: Foldable t => t a -> [a]
-- `concat` :: Foldable t => t [a] -> [a]
-- `concatMap` :: Foldable t => (a -> [b]) -> t a -> [b]
-- @
--------------
-- $shortcircuit
--
-- #short#
-- Examples of short-cicuit reduction include various boolean predicates that
-- test whether some or all the elements of a structure satisfy a given
-- condition. Because these don't necessarily consume the entire list, they
-- typically employ `foldr` with an operator that is conditionally strict in
-- its second argument. Once the termination condition is met the second
-- argument (tail of the input structure) is ignored. No result is returned
-- until that happens.
--
-- The key distinguishing feature of these folds is /conditional/ strictness
-- in the second argument, it is sometimes evaluated and sometimes not.
--
-- The simplest (degenerate case) of these is 'null', which determines whether
-- a structure is empty or not. This only needs to look at the first element,
-- and only to the extent of whether it exists or not, and not its value. In
-- this case termination is guaranteed, and infinite input structures are fine.
-- Its default definition is of course in terms of the lazy 'foldr':
--
-- > null = foldr (\_ _ -> False) True
--
-- A more general example is `any`, which applies a predicate to each input
-- element in turn until it finds the first one for which the predicate is
-- true, at which point it returns success. If, in an infinite input stream
-- the predicate is false for all the elements, `any` will not terminate,
-- but since it runs in constant space, it typically won't run out of memory,
-- it'll just loop forever.
--------------
-- $shortlist
--
-- The full list of short-circuit folds in this module is:
--
-- * Boolean predicate folds.
-- These functions examine elements strictly until a condition is met,
-- but then return a result ignoring the rest (lazy in the tail). These
-- may loop forever given an unbounded input where no elements satisy the
-- termination condition.
--
-- @
-- `null` :: Foldable t => t a -> Bool
-- `elem` :: Foldable t => Eq a => a -> t a -> Bool
-- `notElem` :: (Foldable t, Eq a) => a -> t a -> Bool
-- `and` :: Foldable t => t Bool -> Bool
-- `or` :: Foldable t => t Bool -> Bool
-- `find` :: Foldable t => (a -> Bool) -> t a -> Maybe a
-- `any` :: Foldable t => (a -> Bool) -> t a -> Bool
-- `all` :: Foldable t => (a -> Bool) -> t a -> Bool
-- @
--
-- * Many instances of @('<|>')@ (e.g. the 'Maybe' instance) are conditionally
-- lazy, and use or don't use their second argument depending on the value
-- of the first. These are used with the folds below, which terminate as
-- early as possible, but otherwise generally keep going. Some instances
-- (e.g. for List) are always strict, but the result is lazy in the tail
-- of the output, so that `asum` for a list of lists is in fact corecursive.
-- These folds are defined in terms of `foldr`.
--
-- @
-- `asum` :: (Foldable t, Alternative f) => t (f a) -> f a
-- `msum` :: (Foldable t, MonadPlus m) => t (m a) -> m a
-- @
--
-- * Likewise, the @('*>')@ operator in some `Applicative` functors, and @('>>')@
-- in some monads are conditionally lazy and can /short-circuit/ a chain of
-- computations. The below folds will terminate as early as possible, but
-- even infinite loops can be productive here, when evaluated solely for
-- their stream of IO side-effects. See "Data.Traversable#validation"
-- for some additional discussion.
--
-- @
-- `traverse_` :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()
-- `for_` :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f ()
-- `sequenceA_` :: (Foldable t, Applicative f) => t (f a) -> f ()
-- `mapM_` :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()
-- `forM_` :: (Foldable t, Monad m) => t a -> (a -> m b) -> m ()
-- `sequence_` :: (Foldable t, Monad m) => t (m a) -> m ()
-- @
--
-- * Finally, there's one more special case, `foldlM`, which can short-circuit
-- when the monad @m@ is a 'MonadPlus', and the operator invokes 'mzero'.
--
-- @`foldlM` :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b@
--
-- This type of fold is right-associative in the monadic effects, and
-- left-associative in the output value.
--
-- Given a structure @t@ with elements @(a, b, ..., x, y)@, the result
-- of a fold with operator @f@ is equivalent to:
--
-- > foldlM f z t = do { aa <- f z a; bb <- f aa b; ... ; f xx y }
--
-- If in a 'MonadPlus' the bind short-circuits, the evaluated effects will
-- be from an initial portion of the sequence.
--
-- >>> :set -XBangPatterns
-- >>> import Control.Monad
-- >>> import Control.Monad.Trans.Class
-- >>> import Control.Monad.Trans.Maybe
-- >>> import Data.Foldable
-- >>> let f !_ e = when (e > 3) mzero >> lift (print e)
-- >>> runMaybeT $ foldlM f () [0..]
-- 0
-- 1
-- 2
-- 3
-- Nothing
--
-- Contrast this with `foldrM`, which uses `foldl` to sequence the effects,
-- and therefore diverges (running out of space) when given an unbounded
-- input structure. The short-circuit condition is never reached
--
-- >>> let f e _ = when (e > 3) mzero >> lift (print e)
-- >>> runMaybeT $ foldrM f () [0..]
-- ...hangs...
--
-- If instead the operator short-circuits on the initial elements and the
-- structure is finite, `foldrM` will perform the monadic effects in reverse
-- order:
--
-- >>> let f e _ = when (e < 3) mzero >> lift (print e)
-- >>> runMaybeT $ foldrM f () [0..5]
-- 5
-- 4
-- 3
-- Nothing
--------------
-- $hybrid
--
-- The below folds, are neither strict reductions that produce a final answer
-- in constant space, nor lazy corecursions, and so have limited applicability.
-- They do have specialised uses, but are best avoided when in doubt.
--
-- @
-- 'foldr'' :: (a -> b -> b) -> b -> t a -> b
-- `foldl` :: (b -> a -> b) -> b -> t a -> b
-- `foldl1` :: (a -> a -> a) -> t a -> a
-- `foldrM` :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
-- @
--
-- The lazy left-folds (used corecursively) and 'foldrM' (used to sequence
-- actions right-to-left) can be efficient in structures whose @Foldable@
-- instances take advantage of efficient right-to-left iteration to perform
-- lazy left folds outside-in from the right-most element.
--
-- The strict 'foldr'' is the least likely to be useful, structures that
-- support efficient sequencing /only/ right-to-left are not at all common.
--------------
-- $instances
--
-- #instances#
-- For many structures reasonably efficient @Foldable@ instances can be derived
-- automatically, by enabling the @DeriveFoldable@ GHC extension. When this
-- works, it is generally not necessary to define a custom instance by hand.
-- Though in some cases one may be able to get slightly faster hand-tuned code,
-- care is required to avoid producing slower code, or code that is not
-- sufficiently lazy, strict or /lawful/.
--
-- The hand-crafted instances can get away with only defining one of 'foldr' or
-- 'foldMap'. All the other methods have default definitions in terms of one
-- of these. The default definitions have the expected strictness and the
-- expected asymptotic runtime and space costs, modulo small constant factors.
-- If you choose to hand-tune, benchmarking is advised to see whether you're
-- doing better than the default derived implementations, plus careful tests to
-- ensure that the custom methods are correct.
--
-- Below we construct a @Foldable@ instance for a data type representing a
-- (finite) binary tree with depth-first traversal.
--
-- > data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
-- a suitable instance would be:
--
-- > instance Foldable Tree where
-- > foldr f z Empty = z
-- > foldr f z (Leaf x) = f x z
-- > foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--
-- The 'Node' case is a right fold of the left subtree whose initial
-- value is a right fold of the rest of the tree.
--
-- For example, when @f@ is @(':')@, all three cases return an immediate value,
-- respectively @z@ or a /cons cell/ holding @x@ or @l@, with the remainder the
-- structure, if any, encapsulated in a lazy thunk. This meets the expected
-- efficient [corecursive](#corec) behaviour of 'foldr'.
--
-- Alternatively, one could define @foldMap@:
--
-- > instance Foldable Tree where
-- > foldMap f Empty = mempty
-- > foldMap f (Leaf x) = f x
-- > foldMap f (Node l k r) = foldMap f l <> f k <> foldMap f r
--
-- And indeed some efficiency may be gained by directly defining both,
-- avoiding some indirection in the default definitions that express
-- one in terms of the other. If you implement just one, likely 'foldr'
-- is the better choice.
--
-- A binary tree typically (when balanced, or randomly biased) provides equally
-- efficient access to its left and right subtrees. This makes it possible to
-- define a `foldl` optimised for [corecursive](#corec) folds with operators
-- that are lazy in their first (left) argument.
--
-- > instance Foldable Tree where
-- > foldr f z Empty = z
-- > foldr f z (Leaf x) = f x z
-- > foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
-- > --
-- > foldMap f Empty = mempty
-- > foldMap f (Leaf x) = f x
-- > foldMap f (Node l k r) = foldMap f l <> f k <> foldMap f r
-- > --
-- > foldl f z Empty = z
-- > foldl f z (Leaf x) = f z x
-- > foldl f z (Node l k r) = foldl f (f (foldl f z l) k) r
--
-- Now left-to-right and right-to-left iteration over the structure
-- elements are equally efficient (note the mirror-order output when
-- using `foldl`):
--
-- >>> foldr (\e acc -> e : acc) [] (Node (Leaf 1) 2 (Leaf 3))
-- [1,2,3]
-- >>> foldl (\acc e -> e : acc) [] (Node (Leaf 1) 2 (Leaf 3))
-- [3,2,1]
--
-- We can carry this further, and define more non-default methods...
--
-- The structure definition actually admits trees that are unbounded on either
-- or both sides. The only fold that can plausibly terminate for a tree
-- unbounded on both left and right is `null`, when defined as shown below.
-- The default definition in terms of `foldr` diverges if the tree is unbounded
-- on the left. Here we define a variant that avoids travelling down the tree
-- to find the left-most element and just examines the root node.
--
-- > null Empty = True
-- > null _ = False
--
-- This is a sound choice also for finite trees.
--
-- In practice, unbounded trees are quite uncommon, and can barely be said to
-- be @Foldable@. They would typically employ breadth first traversal, and
-- would support only corecursive and short-circuit folds (diverge under strict
-- reduction).
--
-- Returning to simpler instances, defined just in terms of `foldr`, it is
-- somewhat surprising that a fairly efficient /default/ implementation of the
-- strict 'foldl'' is defined in terms of lazy `foldr` when only the latter is
-- explicitly provided by the instance. It may be instructive to take a look
-- at how this works.
--------------
-- $strictlazy
--
-- #strictlazy#
--
-- The left fold:
--
-- @foldl' f z [a, b, …, x, y]@
--
-- can be expanded as:
--
-- @
-- id . g y . g x . … . g b . g a $ z
-- where g = flip f
-- @
--
-- In which to maintain the expected strictness we need to perform function
-- application eagerly, and composition lazily. To that end we introduce a new
-- function @f'@ which maps each element @x@ to an eager application of @g x@
-- to its argument, followed by an application of a lazily computed composition
-- (@k@) of the @g e@ functions for the remaining elements @e@:
--
-- > f' x k z = k $! (g x) z = k $! f z x
--
-- We see that a lazy 'foldr' of the @g e@ endomorphisms, with @f'@ as as the
-- operator, in fact yields a strict left fold, that avoids building a
-- deep chain of intermediate thunks:
--
-- > foldl' f z0 xs = foldr f' id xs z0
-- > where f' x k z = k $! f z x
--
-- The function applied to @z0@ is built corecursively, and its terms are
-- applied eagerly to the accumulator before further terms are applied to
-- the result. So, as promised, this will run in constant space, and GHC
-- is able to optimise this to an efficient loop.
--------------
-- $generative
--
-- #generative#
-- So far, we have not discussed /generative recursion/. Unlike recursive
-- reduction or corecursion, instead of processing a sequence of elements
-- already in memory, generative recursion involves producing a possibly
-- unbounded sequence of values from an initial seed value. The canonical
-- example of this is 'Data.List.unfoldr' for Lists, with variants available
-- for Vectors and various other structures.
--
-- A key issue with lists, when used generatively as /iterators/, rather than as
-- poor-man's containers (see [[1\]](#uselistsnot)), is that such iterators
-- tend to consume memory when used more than once. A single traversal of a
-- list-as-iterator will run in constant space, but as soon as the list is
-- retained for reuse, its entire element sequence is stored in memory, and the
-- second traversal reads the copy, rather than regenerates the elements. It
-- is sometimes better to recompute the elements rather than memoise the list.
--
-- Memoisation happens because the built-in Haskell list __@[]@__ is
-- represented as __data__, either empty or a /cons-cell/ holding the first
-- element and the tail of the list. The @Foldable@ class enables a variant
-- representation of iterators as /functions/, which take an operator and a
-- starting accumulator and output a summary result.
--
-- The [@fmlist@](https://hackage.haskell.org/package/fmlist) package takes
-- this approach, by representing a list via its `foldMap` action.
--
-- Below we implement an analogous data structure using a representation
-- based on `foldr`. This is an example of /Church encoding/
-- (named after Alonzo Church, inventor of the lambda calculus).
--
-- > {-# LANGUAGE RankNTypes #-}
-- > newtype FRList a = FR { unFR :: forall b. (a -> b -> b) -> b -> b }
--
-- The __@unFR@__ field of this type is essentially its `foldr` method
-- with the list as its first rather than last argument. Thus we
-- immediately get a @Foldable@ instance (and a 'toList' function
-- mapping an __@FRList@__ to a regular list).
--
-- > instance Foldable FRList where
-- > foldr f z l = unFR l f z
-- > -- With older versions of @base@, also define sum, product, ...
-- > -- to ensure use of the strict 'foldl''.
-- > -- sum = foldl' (+) 0
-- > -- ...
--
-- We can convert a regular list to an __@FRList@__ with:
--
-- > fromList :: [a] -> FRList a
-- > fromList as = FRList $ \ f z -> foldr f z as
--
-- However, reuse of an __@FRList@__ obtained in this way will typically
-- memoise the underlying element sequence. Instead, we can define
-- __@FRList@__ terms directly:
--
-- > -- | Immediately return the initial accumulator
-- > nil :: FRList a
-- > nil = FRList $ \ _ z -> z
-- > {-# INLINE nil #-}
--
-- > -- | Fold the tail to use as an accumulator with the new initial element
-- > cons :: a -> FRList a -> FRList a
-- > cons a l = FRList $ \ f z -> f a (unFR l f z)
-- > {-# INLINE cons #-}
--
-- More crucially, we can also directly define the key building block for
-- generative recursion:
--
-- > -- | Generative recursion, dual to `foldr`.
-- > unfoldr :: (s -> Maybe (a, s)) -> s -> FRList a
-- > unfoldr g s0 = FR generate
-- > where generate f z = loop s0
-- > where loop s | Just (a, t) <- g s = f a (loop t)
-- > | otherwise = z
-- > {-# INLINE unfoldr #-}
--
-- Which can, for example, be specialised to number ranges:
--
-- > -- | Generate a range of consecutive integral values.
-- > range :: (Ord a, Integral a) => a -> a -> FRList a
-- > range lo hi =
-- > unfoldr (\s -> if s > hi then Nothing else Just (s, s+1)) lo
-- > {-# INLINE range #-}
--
-- The program below, when compiled with optimisation:
--
-- > main :: IO ()
-- > main = do
-- > let r :: FRList Int
-- > r = range 1 10000000
-- > in print (sum r, length r)
--
-- produces the expected output with no noticeable garbage-collection, despite
-- reuse of the __@FRList@__ term __@r@__.
--
-- > (50000005000000,10000000)
-- > 52,120 bytes allocated in the heap
-- > 3,320 bytes copied during GC
-- > 44,376 bytes maximum residency (1 sample(s))
-- > 25,256 bytes maximum slop
-- > 3 MiB total memory in use (0 MB lost due to fragmentation)
--
-- The Weak Head Normal Form of an __@FRList@__ is a lambda abstraction not a
-- data value, and reuse does not lead to memoisation. Reuse of the iterator
-- above is somewhat contrived, when computing multiple folds over a common
-- list, you should generally traverse a list only [once](#multipass). The
-- goal is to demonstrate that the separate computations of the 'sum' and
-- 'length' run efficiently in constant space, despite reuse. This would not
-- be the case with the list @[1..10000000]@.
--
-- This is, however, an artificially simple reduction. More typically, there
-- are likely to be some allocations in the inner loop, but the temporary
-- storage used will be garbage-collected as needed, and overall memory
-- utilisation will remain modest and will not scale with the size of the list.
--
-- If we go back to built-in lists (i.e. __@[]@__), but avoid reuse by
-- performing reduction in a single pass, as below:
--
-- > data PairS a b = P !a !b -- We define a strict pair datatype
-- >
-- > main :: IO ()
-- > main = do
-- > let l :: [Int]
-- > l = [1..10000000]
-- > in print $ average l
-- > where
-- > sumlen :: PairS Int Int -> Int -> PairS Int Int
-- > sumlen (P s l) a = P (s + a) (l + 1)
-- >
-- > average is =
-- > let (P s l) = foldl' sumlen (P 0 0) is
-- > in (fromIntegral s :: Double) / fromIntegral l
--
-- the result is again obtained in constant space:
--
-- > 5000000.5
-- > 102,176 bytes allocated in the heap
-- > 3,320 bytes copied during GC
-- > 44,376 bytes maximum residency (1 sample(s))
-- > 25,256 bytes maximum slop
-- > 3 MiB total memory in use (0 MB lost due to fragmentation)
--
-- (and, in fact, faster than with __@FRList@__ by a small factor).
--
-- The __@[]@__ list structure works as an efficient iterator when used
-- just once. When space-leaks via list reuse are not a concern, and/or
-- memoisation is actually desirable, the regular list implementation is
-- likely to be faster. This is not a suggestion to replace all your uses of
-- __@[]@__ with a generative alternative.
--
-- The __@FRList@__ type could be further extended with instances of 'Functor',
-- 'Applicative', 'Monad', 'Alternative', etc., and could then provide a
-- fully-featured list type, optimised for reuse without space-leaks. If,
-- however, all that's required is space-efficient, re-use friendly iteration,
-- less is perhaps more, and just @Foldable@ may be sufficient.
--------------
-- $multipass
--
-- #multipass#
-- In applications where you want to compute a composite function of a
-- structure, which requires more than one aggregate as an input, it is
-- generally best to compute all the aggregates in a single pass, rather
-- than to traverse the same structure repeatedly.
--
-- The [@foldl@](http://hackage.haskell.org/package/foldl) package implements a
-- robust general framework for dealing with this situation. If you choose to
-- to do it yourself, with a bit of care, the simplest cases are not difficult
-- to handle directly. You just need to accumulate the individual aggregates
-- as __strict__ components of a single data type, and then apply a final
-- transformation to it to extract the composite result. For example,
-- computing an average requires computing both the 'sum' and the 'length' of a
-- (non-empty) structure and dividing the sum by the length:
--
-- > import Data.Foldable (foldl')
-- >
-- > data PairS a b = P !a !b -- We define a strict pair datatype
-- >
-- > -- | Compute sum and length in a single pass, then reduce to the average.
-- > average :: (Foldable f, Fractional a) => f a -> a
-- > average xs =
-- > let sumlen (P s l) a = P (s + a) (l + 1 :: Int)
-- > (P s l) = foldl' sumlen (P 0 0) xs
-- > in s / fromIntegral l
--
-- The above example is somewhat contrived, some structures keep track of their
-- length internally, and can return it in \(\mathcal{O}(1)\) time, so this
-- particular recipe for averages is not always the most efficient. In
-- general, composite aggregate functions of large structures benefit from
-- single-pass reduction. This is especially the case when reuse of a list and
-- memoisation of its elements is thereby avoided,
--------------
-- $laws
--
-- @Foldable@ instances are expected to satisfy the following laws:
--
-- > foldr f z t = appEndo (foldMap (Endo . f) t ) z
--
-- > foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--
-- > fold = foldMap id
--
-- > length = getSum . foldMap (Sum . const 1)
--
-- @sum@, @product@, @maximum@, and @minimum@ should all be essentially
-- equivalent to @foldMap@ forms, such as
--
-- > sum = getSum . foldMap' Sum
-- > product = getProduct . foldMap' Product
--
-- but are generally more efficient when defined more directly as:
--
-- > sum = foldl' (+) 0
-- > sum = foldl' (*) 1
--
-- If the type is also a 'Functor' instance, it should satisfy
--
-- > foldMap f = fold . fmap f
--
-- which implies that
--
-- > foldMap f . fmap g = foldMap (f . g)
--
--------------
-- $notes
--
-- #notes#
-- The absence of a 'Functor' superclass allows
-- @Foldable@ structures to impose constraints on their element types. Thus,
-- Sets are @Foldable@, even though @Set@ imposes an 'Ord' constraint on its
-- elements (this precludes defining a @Functor@ instance for @Set@).
--
-- The @Foldable@ class makes it possible to use idioms familiar from the List
-- type with container structures that are better suited to the task at hand.
-- This allows a user to substitute more appropriate @Foldable@ data types
-- for Lists without requiring new idioms (see [[1\]](#uselistsnot) for when
-- not to use lists).
--
-- The more general methods of the @Foldable@ class are now exported by the
-- "Prelude" in place of the original List-specific methods (see the
-- [FTP Proposal](https://wiki.haskell.org/Foldable_Traversable_In_Prelude)).
-- The List-specific variants are still available in "Data.List".
--
-- Surprises can arise from the @Foldable@ instance of the 2-tuple @(a,)@ which
-- now behaves as a 1-element @Foldable@ container in its second slot. In
-- contexts where a specific monomorphic type is expected, and you want to be
-- able to rely on type errors to guide refactoring, it may make sense to
-- define and use less-polymorphic variants of some of the @Foldable@ methods.
--
-- Below are two examples showing a definition of a reusable less-polymorphic
-- 'sum' and a one-off in-line specialisation of 'length':
--
-- > {-# LANGUAGE TypeApplications #-}
-- >
-- > mySum :: Num a => [a] -> a
-- > mySum = sum
-- >
-- > type SlowVector a = [a]
-- > slowLength :: SlowVector -> Int
-- > slowLength v = length @[] v
--
-- In both cases, if the data type to which the function is applied changes
-- to something other than a list, the call-site will no longer compile until
-- appropriate changes are made.
--------------
-- $also
--
-- * [1] #uselistsnot# \"When You Should Use Lists in Haskell (Mostly, You Should Not)\",
-- by Johannes Waldmann,
-- in arxiv.org, Programming Languages (cs.PL), at
-- <https://arxiv.org/abs/1808.08329>.
--
-- * [2] \"The Essence of the Iterator Pattern\",
-- by Jeremy Gibbons and Bruno Oliveira,
-- in /Mathematically-Structured Functional Programming/, 2006, online at
-- <http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/#iterator>.
|