Skip to content

GitLab

  • Projects
  • Groups
  • Snippets
  • Help
    • Loading...
  • Help
    • Help
    • Support
    • Community forum
    • Submit feedback
  • Sign in / Register
GHC
GHC
  • Project overview
    • Project overview
    • Details
    • Activity
    • Releases
  • Repository
    • Repository
    • Files
    • Commits
    • Branches
    • Tags
    • Contributors
    • Graph
    • Compare
    • Locked Files
  • Issues 4,394
    • Issues 4,394
    • List
    • Boards
    • Labels
    • Service Desk
    • Milestones
    • Iterations
  • Merge Requests 377
    • Merge Requests 377
  • Requirements
    • Requirements
    • List
  • CI / CD
    • CI / CD
    • Pipelines
    • Jobs
    • Schedules
    • Test Cases
  • Operations
    • Operations
    • Incidents
    • Environments
  • Analytics
    • Analytics
    • CI / CD
    • Code Review
    • Insights
    • Issue
    • Repository
    • Value Stream
  • Wiki
    • Wiki
  • Snippets
    • Snippets
  • Members
    • Members
  • Activity
  • Graph
  • Create a new issue
  • Jobs
  • Commits
  • Issue Boards
Collapse sidebar
  • Glasgow Haskell Compiler
  • GHCGHC
  • Issues
  • #9369

Closed
Open
Opened Jul 27, 2014 by David Feuer@treeowlReporter

Data.List.unfoldr does not fuse and is not inlined.

Data.List.unfoldr is not a good producer for foldr/build fusion, and it's not wrapped to enable inlining. I don't know how often people explicitly fold over an unfold, but this of course also affects map and filter. The inlining issue is also serious: inlining unfoldr can often allow the Maybe to be erased altogether. I'm not sure this fix is perfect, but it seems a lot better than the current situation:

import GHC.Exts (build)

{-# NOINLINE [1] unfoldr #-}
unfoldr :: (b -> Maybe (a, b)) -> b -> [a]
unfoldr f b = go b
  where
    go b = case f b of
             Just (a,new_b) -> a : go new_b
             Nothing -> []

{-# INLINE [0] unfoldrB #-}
unfoldrB :: (b -> Maybe (a, b)) -> b -> (a -> c -> c) -> c -> c
unfoldrB f b' c n = go b'
  where
    go b = case f b of
             Just (a,new_b) -> a `c` go new_b
             Nothing        -> n

{-# RULES
"unfoldr"  [~1] forall f b . unfoldr f b = build (unfoldrB f b)
 #-}

As a simple example, consider the code

hello :: Double -> Double -> [Double]
hello x n = map (* 3) $ L.unfoldr f x
  where
    f x | x < n     = Just (x, x**1.2)
        | otherwise = Nothing

With Data.List.unfoldr and the latest bleeding-edge GHC, this produces

hello1
hello1 =
  \ ds_d1ZF -> case ds_d1ZF of _ { D# x_a21W -> D# (*## x_a21W 3.0) }

$whello
$whello =
  \ w_s266 ww_s26a ->
    map
      hello1
      (unfoldr
         (\ x_X1Hx ->
            case x_X1Hx of wild_a20E { D# x1_a20G ->
            case tagToEnum# (<## x1_a20G ww_s26a) of _ {
              False -> Nothing;
              True -> Just (wild_a20E, D# (**## x1_a20G 1.2))
            }
            })
         w_s266)

hello
hello =
  \ w_s266 w1_s267 ->
    case w1_s267 of _ { D# ww1_s26a -> $whello w_s266 ww1_s26a }

Using the above implementation (and renaming the function from hello to bye) yields

$wbye
$wbye =
  \ ww_s25Z ww1_s263 ->
    letrec {
      $wgo_s25U
      $wgo_s25U =
        \ ww2_s25S ->
          case tagToEnum# (<## ww2_s25S ww1_s263) of _ {
            False -> [];
            True -> : (D# (*## ww2_s25S 3.0)) ($wgo_s25U (**## ww2_s25S 1.2))
          }; } in
    $wgo_s25U ww_s25Z

bye
bye =
  \ w_s25V w1_s25W ->
    case w_s25V of _ { D# ww1_s25Z ->
    case w1_s25W of _ { D# ww3_s263 -> $wbye ww1_s25Z ww3_s263 }
    }

I don't think there can be any doubt which is better. Yes, some fine tuning may be needed to make the rules apply in all appropriate cases. I don't understand things like the comment on the definition of map drawing attention to eta expansion.

Trac metadata
Trac field Value
Version 7.8.3
Type Bug
TypeOfFailure OtherFailure
Priority normal
Resolution Unresolved
Component libraries/base
Test case
Differential revisions
BlockedBy
Related
Blocking
CC ekmett, hvr
Operating system
Architecture
Assignee
Assign to
7.10.1
Milestone
7.10.1 (Past due)
Assign milestone
Time tracking
None
Due date
None
Reference: ghc/ghc#9369