haskell# Haskell's reducing rule

How does `lengthGT4 $ produce id 1`

reduced to `True`

in Haskell?

```
lengthGT4 :: List a -> Bool
lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True
lengthGT4 (_ :. _) = False -- deliberately doing this
produce :: (a -> a) -> a -> List a
produce f i = i :. produce f (f i)
lengthGT4 $ produce id 1
```

`$`

puts right-hand statement as left first parameter.

- On reducing, when
`$`

takes right-hand to left for matching? Why right-hand`product`

doesn't expand infinitely and doesn't prevent`$`

from taking and matching? - Why following
`not jump`

doesn't match`lengthGT4 (_ :. _) = False`

and turns out`False`

? While`here jump out`

matchs`lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True`

and turns out`True`

?

```
lengthGT4 $ 1 :. (produce id 1) -- not jump
lengthGT4 $ 1 :. 1:. (produce id 1)
lengthGT4 $ 1 :. 1:. 1:. (produce id 1)
lengthGT4 $ 1 :. 1:. 1:. 1:. (produce id 1) -- here jump out
```

Coming from `fp-course`

https://github.com/Nero5023/fp-course-solution/blob/f95a1a8c1b95dbe63015168f4fe4388854cd4a32/src/Course/List.hs#L280

Solution

- On reducing, when
`$`

takes right-hand to left for matching? Why right-hand`product`

doesn't expand infinitely and doesn't prevent`$`

from taking and matching?

You can pretend that the `$`

in the expression `e1 $ e2`

does not evaluate the expressions `e1`

and `e2`

before reducing. Effectively, `e1 $ e2`

reduces to the function application `e1 e2`

, and that will then evaluate and apply the function `e1`

to the *unevaluated* expression `e2`

.

Note that it's the function `e1`

that decides how much `e2`

gets evaluated. That's how laziness works. For example, `take 3 (1:2:3:4:error "urk")`

does not evaluate the `error`

, so the program does not crash and evaluates to `[1,2,3]`

. By contrast, `take 7 (1:2:3:4:error "urk")`

does crash.

In your case, `produce id 1`

is not evaluated by `$`

. Instead, it is evaluated according to `lengthGT4`

, and only as much as needed to match or refute the patterns. Hence, it never gets fully evaluated to an infinite list (which would make the program run forever).

- Why following
`not jump`

doesn't match`lengthGT4 (_ :. _) = False`

and turns out`False`

? While`here jump out`

matchs`lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True`

and turns out`True`

?

Patterns are tried in-order, from top to bottom. Effectively, a definition like

```
f pat1 = exp1
f pat2 = exp2
...
```

Means, in pseudo-code:

```
Take the input argument of f.
Evaluate the input as much as needed to match or refute pat1.
if it's a match then
Bind variables of pat1 to the corresponding values.
Evaluate exp1 and return the result.
else
Evaluate the input as much as needed to match or refute pat2.
if it's a match then
Bind variables of pat2 to the corresponding values.
Evaluate exp2 and return the result.
else
...
```

In your specific case, the pattern in `lengthGT4 (_ :. _) = False`

is not considered until the pattern in `lengthGT4 (_ :. _ :. _ :. _ :. _ :. _) = True`

is refuted. But that is not refuted for that input `produce id 1`

, since it can evaluate to a list with at least 5 elements.

- Haskell - QuickCheck: Checking Equality in TestTree
- Binary Tree pre order transversal
- rankN type equivalent for mypy in python
- How to solve basic error compile in haskell
- Lack of Finite Element Method implementations in Haskell - Any specific reasons?
- How does the function composition (.) operator work with multiple compositions?
- Is possible code haskell and run it in github codespace?
- Scotty: No instance for MonadIO ScottyT (arising from a use of ‘liftIO’)
- Deserializing JSON file with aeson in Haskell
- How can I implement a splay tree that performs the zig operation last, not first?
- What is fusion in Haskell?
- General approach for combining multiple foldrs over the accumulator type?
- using Lens for nested folds with a threaded accumulator
- What is the difference between . (dot) and $ (dollar sign)?
- understand haskell logic behind odd's and even's index lists
- Java tagged union / sum types
- Is indentation in Haskell like in Python?
- Unicode console I/O in Haskell on Windows
- Code formatting not working with Pandoc in Haskell
- How can I use `liftIO` with State to print values inside that Monad?
- Module X appears in multiple packages
- High order function returning result and modified itself
- Parsec not parsing newline character
- Enable -Woverflowed-literals for custom numeric types
- How to format UTCTime as ISO 8601 in Haskell
- Haskell Depth-First Graph Traversal has Infinite Loop
- Non-exhaustive patterns in function defined in GHCi
- How to run an individual test with Stack and Haskell Test.Framework?
- Persisting drawn frames in Gloss
- How do I convert from unixtime to a date/time in Haskell?