Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Ranges in Haskell (GHCi)

Tags:

haskell

I'm reading Learn You A Haskell for Great Good. His examples [2,2..20] and [3, 6..20] work fine but I got three weird results:

  1. Count by 17's from one to 171: [17, 1..171] yields the null list.
  2. Count by 17's from seventeen to 1711111: [17, 17..171111] repeats the number 17 until I interrupt GHCi.
  3. There is a weird difference between take 54 [171, 234..] and take 54 [171, 244..]:

     ghci> take 54 [171, 234..] [171,234,297,360,423,486,549,612,675,738,801,864,927,990,1053,1116,1179,1242,1305,1368,1431,1494,1557,1620,1683,1746,1809,1872,1935,1998,2061,2124,2187,2250,2313,2376,2439,2502,2565,2628,2691,2754,2817,2880,2943,3006,3069,3132,3195,3258,3321,3384,3447,3510]   ghci> take 54 [171, 244..] [171,244,317,390,463,536,609,682,755,828,901,974,1047,1120,1193,1266,1339,1412,1485,1558,1631,1704,1777,1850,1923,1996,2069,2142,2215,2288,2361,2434,2507,2580,2653,2726,2799,2872,2945,3018,3091,3164,3237,3310,3383,3456,3529,3602,3675,3748,3821,3894,3967,4040] 

Why?

like image 363
isomorphismes Avatar asked Oct 31 '11 18:10

isomorphismes


People also ask

What does ++ mean in Haskell?

The ++ operator is the list concatenation operator which takes two lists as operands and "combine" them into a single list.

How is list defined in Haskell?

Introduction to Haskell list. In Haskell list is used to store the elements, and these elements are homogenous in nature which simply means only one type. Inside the list, we can store the list of elements that are of the same type. we can store any data type inside the list.

How do I use a map in Haskell?

map is a function that takes two parameters: a function and a list of elements. The type signature of map is (a -> b) -> [a] -> [b] . The (a -> b) part is the function you pass to map , we will call it f . f takes one value and returns another that may be of a different type.


2 Answers

You have the meaning of ranges slightly off. The Haskell range syntax is one of four things: [first..], [first,second..], [first..last], [first,second..last]. The examples from Learn You A Haskell are

ghci> [2,4..20]   [2,4,6,8,10,12,14,16,18,20]   ghci> [3,6..20]   [3,6,9,12,15,18]    

Note that in the first case, the list counts by twos, and in the second case, the list counts by threes. That's because the difference between the first and second items is two and three, respectively. In your syntax, you're trying to write [first,step..last] to get the list [first,first+step,first+2*step,...,last]; however, the step size of a range like that is actually the difference between the first two numbers. Without a second element, the step size is always one; and without a final element, the list goes on forever (or until the maximum/minimum element of the type is reached).

Thus, let's look at your three examples:

  • [17,1..171] == []. Since you specify 17,1, Haskell sees that the first two elements of your list ought to be seventeen and one, so you must be counting by -16. In that case, Haskell wants to stop as soon as the elements are smaller than the last element---but they start that way, and so no elements are produced. To count up by one, you want [17,18..171] (the first two elements of your list are 17 and 18), or simply [17..171].

  • [17, 17..171111] == repeat 17. This one's fun. Since the first two elements of your list are both 17, Haskell determines that you must be counting up by zero—and it will happily keep counting up until the result exceeds 171111. Of course, when counting by zero, this will never happen, and so you get an infinite list of seventeens. To count up by seventeen, you want [17,34..171111], or [17,17+17..171111] if you think that's clearer.

  • take 54 [171,234..] vs. take 54 [171,244..]. I'm not sure what behavior you were expecting here, but what they're each doing is the same as above: the first returns a list of fifty-four integers, starting at 171 and counting by 234 - 171 = 63; the second returns a list of fifty-four integers, starting at 171 and counting by 244 - 171 = 73. Each list goes on infinitely far (or at least until maxBound, if the lists are of finite Ints and not arbitrarily-large Integers), and so you just request the first fifty-four elements.

For some of the more nitty-gritty details on what range syntax means (it's translated into functions in the Enum type class), including slightly surprising behavior on ranges of floating-point numbers, hammar has a good answer to another question.

like image 81
Antal Spector-Zabusky Avatar answered Sep 19 '22 18:09

Antal Spector-Zabusky


Well, the semantics of those operations are a little bit different than you expect. The construct [a,b..c] is actually just syntactical sugar for enumFromThenTo a b c, which behaves a little bit like this:

Calculate d = b - a. The output of [a,b..c] is [a,a+d,a+d+d,a+d+d+d,...]. This is repeated, till a+n*d > c, if d and c - a have different signs (In this case, the list would be infinite, so there is no output instead), or till maxBound or minBound is reached, then the output ends. (Of course, this is implemented differently, since we are using arbitrary instances of Enum here).

So [1,3..10] becomes [1,3,5,7,9] and since 17 - 17 = 0, [17, 17..171111] yields [17,17+0,17+0+0...]. And by that slightly complicated rule, [17, 1..171] yields the empty list.

To your addition: [x,y..] is implemented using the function enumFromThen x y, that behaves just like enumFromThenTo, except that there is no boundary condition, so if your Enum is infinite, so will be the resulting list.

like image 33
fuz Avatar answered Sep 23 '22 18:09

fuz